Submission #1062588

#TimeUsernameProblemLanguageResultExecution timeMemory
1062588uacoder123Game (IOI14_game)C++14
42 / 100
1066 ms51684 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; #define F first #define S second #define FOR(i,a,b) for (auto i = (a); i <= (b); ++i) #define NFOR(i,a,b) for(auto i = (a); i >= (b); --i) #define all(x) (x).begin(), (x).end() #define sz(x) lli(x.size()) #define mp(i,a) make_pair(i,a) #define pb(a) push_back(a) #define bit(x,b) (x&(1LL<<b)) typedef int lli; typedef pair <lli,lli> ii; typedef pair <ii,lli> iii; typedef pair <ii,ii> iiii; typedef vector <lli> vi; typedef tree<lli,null_type,less<lli>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; int par[1501],r[1501]; set<ii> s[1501]; int find(int x) { if(par[x]==par[par[x]]) return par[x]; par[x]=find(par[x]); return par[x]; } void m(int a,int b) { for(auto it:s[b]) { s[it.F].erase(mp(b,it.S)); auto it1=s[a].lower_bound(mp(it.F,-1)); s[(*it1).F].erase(mp(a,(*it1).S)); ii f=mp(it.F,it.S+(*it1).S); s[a].erase(it1); s[a].insert(f); s[f.F].insert(mp(a,f.S)); } } void mer(int a,int b) { if(r[a]>=r[b]) { par[b]=a; m(a,b); if(r[a]==r[b]) r[a]++; } else { m(b,a); par[a]=b; } } void initialize(int n) { for(int i=0;i<n;++i) { par[i]=i; r[i]=1; for(int j=i+1;j<n;++j) { s[i].insert(mp(j,1)); s[j].insert(mp(i,1)); } } } int hasEdge(int u, int v) { int pu=find(u),pv=find(v); if(pu==pv) return 0; ii f=(*s[pu].lower_bound(mp(pv,-1))); if(f.S>1) { s[pu].erase(mp(pv,f.S)); s[pv].erase(mp(pu,f.S)); s[pu].insert(mp(pv,f.S-1)); s[pv].insert(mp(pu,f.S-1)); return 0; } s[pu].erase(mp(pv,1)); s[pv].erase(mp(pu,1)); mer(pu,pv); return 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...