Submission #2436717


Source Code Expand

Copy
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(int i = 0; i < n; i++)




class ford_fulkerson
{
private:
    long long inf;  // 初期化に使う値
    struct edge {
        long long to, cap, rev;
    };
    vector<vector<edge>> list;  // グラフの隣接リスト
    vector<long long> level;    // sからの距離
    vector<long long> iter;     // どこまで調べ終わったか
public:
    ford_fulkerson(long long n, long long infinity = 1e16);    // nは頂点の数、infinityは初期化に使う値
    void add_edge(long long from, long long to, long long cap); // fromからtoへ容量capの辺をはる
    void bfs(long long s);  // sからの最短距離を求める
    long long dfs(long long v, long long t, long long f);   // 増加パスをdfsで探す
    long long max_flow(long long s, long long t);   // sからtへの最大流を求める
};

ford_fulkerson::ford_fulkerson(long long n, long long infinity){
    list.resize(n);
    level.resize(n);
    iter.resize(n);
}

void ford_fulkerson::add_edge(long long from, long long to, long long cap){
    list[from].push_back((edge){to, cap, (long long)list[to].size()});
    list[to].push_back((edge){from, 0, (long long)list[from].size() - 1});
}

void ford_fulkerson::bfs(long long s){
    for(long long i = 0; i < level.size(); i++){
        level[i] = -1;
    }
    queue<long long> que;
    level[s] = 0;
    que.push(s);
    while(!que.empty()){
        long long v = que.front(); que.pop();
        for(auto &x : list[v]){
            if(x.cap > 0 && level[x.to] < 0){
                level[x.to] = level[v] + 1;
                que.push(x.to);
            }
        }
    }
}

long long ford_fulkerson::dfs(long long v, long long t, long long f){
    if(v == t)return f;
    
    for(long long &i = iter[v]; i < list[v].size(); i++){
        edge &e = list[v][i];
        if(e.cap > 0 && level[v] < level[e.to]){
            long long d = dfs(e.to, t, min(f, e.cap));
            if(d > 0){
                e.cap -= d;
                list[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

long long ford_fulkerson::max_flow(long long s, long long t){
    long long flow = 0;
    
    for(;;){
        bfs(s);
        if(level[t] < 0)return flow;
        
        for(long long i = 0; i < iter.size(); i++){
            iter[i] = 0;
        }
        
        long long f;
        while((f = dfs(s, t, INF)) > 0){
            flow += f;
        }
    }
}

int main() {
    ll n, a[100], b[100];
    cin >> n;
    ford_fulkerson f(2 * n + 2);
    REP(i, n){
        cin >> a[i] >> b[i];
        f.add_edge(2 * n, i, 1);
    }
    REP(i, n){
        int c, d;
        cin >> c >> d;
        f.add_edge(n + i, 2 * n + 1, 1);
        REP(j, n){
            if(c > a[j] && d > b[j]){
                f.add_edge(j, n + i, 1);
            }
        }
    }
    cout << f.max_flow(2 * n, 2 * n + 1) << endl;
}

Submission Info

Submission Time
Task C - 2D Plane 2N Points
User chocobo
Language C++14 (GCC 5.4.1)
Score 400
Code Size 3488 Byte
Status
Exec Time 2 ms
Memory 512 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example_0, example_1, example_2, example_3, example_4
All 400 / 400 example_0, example_1, example_2, example_3, example_4, line_0, line_1, line_2, line_3, maxrand_0, maxrand_1, maxrand_2, maxrand_3, maxrand_4, rand_0, rand_1, rand_2
Case Name Status Exec Time Memory
example_0 1 ms 256 KB
example_1 1 ms 256 KB
example_2 1 ms 256 KB
example_3 1 ms 256 KB
example_4 1 ms 256 KB
line_0 1 ms 384 KB
line_1 1 ms 256 KB
line_2 1 ms 256 KB
line_3 1 ms 256 KB
maxrand_0 2 ms 384 KB
maxrand_1 2 ms 512 KB
maxrand_2 2 ms 384 KB
maxrand_3 2 ms 512 KB
maxrand_4 2 ms 384 KB
rand_0 2 ms 512 KB
rand_1 1 ms 384 KB
rand_2 1 ms 384 KB