oj.uz

Submission #201768

# Submission time Handle Problem Language Result Execution time Memory
201768 2020-02-12T00:41:21 Z EmmanuelAC Matching (COCI20_matching) C++14
0 / 110
 14 ms 14328 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<long long,long long>
using namespace std;

int N;
vector<pii> pts;
vector<int> vert[200001],
            hor[200001];

vector<int> edges[200001];

bitset<200001> vis;
int par[200001],
    col[200001];

void dfs(int node, int clr){
    if(vis[node])   return;
    vis[node] = true;
    col[node] = clr;

    for(auto u : edges[node])
        dfs(u, 1 -clr);
}

void color(){
    for(int i=0; i<N; i++)  col[i] = -1;

    vis.reset();
    for(int i=0; i<N; i++){
        if(!vis[i]) dfs(i, 1);
    }
}

bool find_path(int node){
    if(vis[node]) return false;
    vis[node] = true;

    for(auto u : edges[node])
        if(par[u] == -1){
            par[u] = node;
            return true;
        }

    for(auto u: edges[node])
        if(find_path(par[u])){
            par[u] = node;
            return true;
        }

    return false;
}

int match(){
    for(int i=0; i<=N; i++) par[i] = -1;

    int num_match = 0;

    for(int i=0; i<N; i++){
        if(par[i] == -1 && col[i] == 1){
            vis.reset();
            if(find_path(i))
                num_match ++;
        }
    }

    return num_match;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;

    pts.resize(N);
    for(int i=0; i<N; i++){
        int a, b; cin >> a >> b;

        vert[a].push_back(i),
        hor[b].push_back(i);

        pts[i] = mp(a, b);
    }

    for(int i=0; i<=N; i++){
        if(vert[i].size() == 2)
            edges[vert[i][0]].push_back(vert[i][1]),
            edges[vert[i][1]].push_back(vert[i][0]);

        if(hor[i].size() == 2)
            edges[hor[i][0]].push_back(hor[i][1]),
            edges[hor[i][1]].push_back(hor[i][0]);
    }

    color();
    int M = match();

    //cout << M << "\n";
    if(M != N/2){
        cout << "NE\n";
        return 0;
    }
    cout << "DA\n";
    for(int i=0; i<=N; i++)  if(par[i] != -1) cout <<  i +1<< " " << par[i] +1<< "\n";

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 14328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 14328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 14328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 14328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 14328 KB Output isn't correct
2 Halted 0 ms 0 KB -