Submission #463663

#TimeUsernameProblemLanguageResultExecution timeMemory
463663JasiekstrzMatching (COCI20_matching)C++17
110 / 110
2491 ms209648 KiB
#include<bits/stdc++.h> #define fi first #define se second using namespace std; const int N=1e5; const int PP=(1<<17); //#warning small constants //const int N=4; //const int PP=4; pair<int,int> tab[N+10]; vector<int> cup[2][N+10]; int cnt[N+10]; int tree[2*PP+10]; bool ok[2*PP+10]; // sat // 2*id - var, 2*id+1 - !var int var[2][N+10]; int neg(int x) { return (x%2==0 ? x+1:x-1); } vector<vector<int>> e; int new_var() { for(int i:{0,1}) e.push_back({}); return e.size()-2; } void new_clause(int a,int b) { //auto debwr=[](int x){ if(x%2==0) cerr<<x<<" "; else cerr<<"!"<<x-1<<" "; return; }; //debwr(a); cerr<<"or "; debwr(b); cerr<<"\n"; e[neg(a)].push_back(b); e[neg(b)].push_back(a); return; } vector<int> low; vector<int> pre; vector<bool> val; vector<bool> vis; vector<bool> on_stack; vector<int> scc; vector<int> stck; vector<int> topo; void dfs1(int x) { static int nr=0,sccnr=0; vis[x]=true; stck.push_back(x); on_stack[x]=true; pre[x]=nr++; low[x]=pre[x]; for(auto v:e[x]) { if(on_stack[v]) low[x]=min(low[x],pre[v]); else if(!vis[v]) { dfs1(v); low[x]=min(low[x],low[v]); } } if(low[x]==pre[x]) { while(on_stack[x]) { int v=stck.back(); stck.pop_back(); scc[v]=sccnr; on_stack[v]=false; } sccnr++; } return; } void dfs2(int x) { vis[x]=true; for(auto v:e[x]) { if(!vis[v]) dfs2(v); } if(low[x]==pre[x]) topo.push_back(x); return; } void dfs3(int x) { vis[x]=true; val[scc[neg(x)]]=!val[scc[x]]; for(auto v:e[x]) { if(!vis[v]) { if(scc[v]==scc[x]) dfs3(v); else if(val[scc[x]]) val[scc[v]]=true; } } return; } vector<bool> solve_2sat() { int n=e.size(); for(auto *vec:{&low,&pre,&scc}) vec->resize(n); for(auto *vec:{&val,&vis,&on_stack}) { vec->resize(n); fill(vec->begin(),vec->end(),false); } for(int i=0;i<n;i++) { if(!vis[i]) dfs1(i); } fill(vis.begin(),vis.end(),false); for(int i=0;i<n;i++) { if(!vis[i]) dfs2(i); } reverse(topo.begin(),topo.end()); fill(vis.begin(),vis.end(),false); for(auto v:topo) { dfs3(v); } //for(int i=0;i<n;i++) // cerr<<"scc["<<i<<"]="<<scc[i]<<" "<<val[scc[i]]<<"\n"; vector<bool> ans(n,false); for(int i=0;i<n;i++) { if(val[scc[i]]==val[scc[neg(i)]]) return {}; for(auto v:e[i]) { if(val[scc[i]] && !val[scc[v]]) return {}; } ans[i]=val[scc[i]]; } return ans; } void new_node(int x) { if(!ok[2*x] && !ok[2*x+1]) { ok[x]=false; tree[x]=-1; return; } ok[x]=true; if(!ok[2*x]) { tree[x]=tree[2*x+1]; return; } if(!ok[2*x+1]) { tree[x]=tree[2*x]; return; } tree[x]=new_var(); new_clause(neg(tree[2*x]),tree[x]); new_clause(neg(tree[2*x+1]),tree[x]); return; } void add_segment(int l,int r,int c) { for(l+=PP-1,r+=PP-1;l<=r;l/=2,r/=2) { if(l%2==1) { if(ok[l]) new_clause(neg(c),neg(tree[l])); l++; } if(r%2==0) { if(ok[r]) new_clause(neg(c),neg(tree[r])); r--; } } return; } void upd_node(int x,int c) { x+=PP-1; ok[x]=(c!=-1); tree[x]=c; for(x/=2;x>0;x/=2) new_node(x); return; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin>>n; for(int i=1;i<=n;i++) { cin>>tab[i].fi>>tab[i].se; cup[0][tab[i].fi].push_back(i); cup[1][tab[i].se].push_back(i); } for(int i=1;i<=N;i++) { var[0][i]=-1; var[1][i]=-1; } for(int i=1;i<=n;i++) { if(var[0][tab[i].fi]==-1) var[0][tab[i].fi]=new_var(); if(var[1][tab[i].se]==-1) var[1][tab[i].se]=new_var(); if(cup[0][tab[i].fi].size()==1 && cup[1][tab[i].se].size()==1) { cout<<"NE\n"; return 0; } else if(cup[0][tab[i].fi].size()==1) new_clause(var[1][tab[i].se],var[1][tab[i].se]); else if(cup[1][tab[i].se].size()==1) new_clause(var[0][tab[i].fi],var[0][tab[i].fi]); else { new_clause(var[0][tab[i].fi],var[1][tab[i].se]); new_clause(neg(var[0][tab[i].fi]),neg(var[1][tab[i].se])); } } for(int i=PP;i<2*PP;i++) { tree[i]=-1; ok[i]=false; } for(int i=PP-1;i>0;i--) new_node(i); for(int i=1;i<=N;i++) { if(cup[1][i].size()==2) { int l=cup[1][i][0],r=cup[1][i][1]; l=tab[l].fi; r=tab[r].fi; if(l>r) swap(l,r); add_segment(l,r,var[1][i]); } for(auto v:cup[1][i]) { v=tab[v].fi; if(cnt[v]==0) upd_node(v,var[0][v]); else upd_node(v,-1); cnt[v]++; } } //for(int i=1;i<=N;i++) //{ // cerr<<"fi="<<i<<": "<<var[0][i]<<"\n"; // cerr<<"se="<<i<<": "<<var[1][i]<<"\n"; //} auto ans=solve_2sat(); if(ans.empty()) { cout<<"NE\n"; return 0; } cout<<"DA\n"; for(int i=1;i<=N;i++) { for(int j:{0,1}) { if(cup[j][i].size()==2 && ans[var[j][i]]) cout<<cup[j][i][0]<<" "<<cup[j][i][1]<<"\n"; } } return 0; }

Compilation message (stderr)

matching.cpp: In function 'int new_var()':
matching.cpp:26:10: warning: unused variable 'i' [-Wunused-variable]
   26 |  for(int i:{0,1})
      |          ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...