Submission #883860

#	Time	Username	Problem	Language	Result	Execution time	Memory
883860		vjudge1	Matching (COCI20_matching)	C++17	5 / 110	4 ms	10864 KiB

matching

#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    const int lim=1e5+100;
#else
    const int lim=2e3+100;
#endif

#include "bits/stdc++.h"
using namespace std;

//#define int long long
#define pb push_back

const int mod=1e9+7;
using pii=pair<int,int>;

struct point{
    int x,y,num;
};
bool used[lim];
point pp[lim];
unordered_set<int>v[lim];
vector<pii>matches;
vector<int>h[lim],w[lim];

void dfs(int node){
    if(used[node])return;
    if(!v[node].size()){
        cout<<"NE";
        exit(0);
    }
    point p=pp[node];
    if(v[node].size()^1)return;
    point mate=pp[*v[node].begin()];
    matches.pb({node,mate.num});
    used[node]=used[mate.num]=1;
    vector<int>nextt;
    if(p.x==mate.x){
        for(int i=p.y;i<=mate.y;i++){
            if(w[i].size()==2&&pp[w[i][0]].x<=p.x&&p.x<=pp[w[i][1]].x){
                v[w[i][0]].erase(w[i][1]);
                v[w[i][1]].erase(w[i][0]);
                nextt.pb(w[i][0]);
                nextt.pb(w[i][1]);
                w[i].clear();
            }
        }
    }
    else{
        for(int i=p.x;i<=mate.x;i++){
            if(h[i].size()==2&&pp[h[i][0]].y<=p.y&&p.y<=pp[h[i][1]].y){
                v[h[i][0]].erase(h[i][1]);
                v[h[i][1]].erase(h[i][0]);
                nextt.pb(h[i][0]);
                nextt.pb(h[i][1]);
                h[i].clear();
            }
        }
    }
    for(int i:nextt){
        if(!used[i])dfs(i);
    }
}

inline void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        pp[i].num=i;
        cin>>pp[i].x>>pp[i].y;
        if(h[pp[i].x].size()){
            v[i].insert(h[pp[i].x][0]);
            v[h[pp[i].x][0]].insert(i);
        }
        h[pp[i].x].pb(i);
        if(w[pp[i].y].size()){
            v[i].insert(w[pp[i].y][0]);
            v[w[pp[i].y][0]].insert(i);
        }
        w[pp[i].y].pb(i);
    }
    for(int i=0;i<n;i++){
        if(h[i].size()==2&&pp[h[i][0]].y>pp[h[i][1]].y){
            swap(h[i][0],h[i][1]);
        }
        if(w[i].size()==2&&pp[w[i][0]].x>pp[w[i][1]].x){
            swap(w[i][0],w[i][1]);
        }
    }
    for(int i=1;i<=n;i++){
        if(used[i])continue;
        dfs(i);
    }
    for(int i=1;i<=n;i++){
        if(!used[i]&&!v[i].size()){
            cout<<"NE";
            return;
        }
        if(!used[i]){
            for(int j:v[i]){
                if(pp[i].x==pp[j].x){
                    matches.pb({i,j});
                    used[i]=used[j]=1;
                }
            }
        }
    }
    cout<<"DA\n";
    for(auto[x,y]:matches){
        cout<<x<<" "<<y<<"\n";
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#else
    //freopen("grass.in","r",stdin);
    //freopen("grass.out","w",stdout);
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 40
• Subtask 5: 0 / 52