Submission #201768

#	Time	Username	Problem	Language	Result	Execution time	Memory
201768		EmmanuelAC	Matching (COCI20_matching)	C++14	0 / 110	14 ms	14328 KiB

matching

#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
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 40
• Subtask 5: 0 / 52