Submission #805714

#TimeUsernameProblemLanguageResultExecution timeMemory
805714Username4132Simurgh (IOI17_simurgh)C++14
100 / 100
142 ms7728 KiB
#include "simurgh.h" #include<iostream> #include<vector> #include<algorithm> #include<set> #include<cassert> using namespace std; using pii = pair<int, int>; #define forn(i, n) for(int i=0; i<(int)n; ++i) #define forsn(i, s, n) for(int i=s; i<(int)n; ++i) #define PB push_back #define F first #define S second int n, m, tm, base, esp[125010], pv[510], pe[510], tin[510]; bool vis[510]; pii edges[125010]; vector<int> ted; vector<vector<int>> uns; vector<pii> g[510]; void dfs(int v){ tin[v]=tm++; vis[v]=true; for(pii to:g[v]) if(!vis[to.F]){ pv[to.F]=v; pe[to.F]=to.S; ted.PB(to.S); dfs(to.F); } } int add_count(int r){ int cou=base; vector<int> ask; forn(i, r){ if(!uns[i].empty()) ask.PB(uns[i].back()), cou-=esp[ted[i]]; else ask.PB(ted[i]); } forsn(i, r, n-1) ask.PB(ted[i]); return count_common_roads(ask) - cou; } void dfs2(int l, int r, int lv, int rv){ if(lv==rv) return; if(r-l==1){ esp[uns[l].back()]=1; return; } int mid = (l+r)>>1, value = add_count(mid); dfs2(l, mid, lv, value); dfs2(mid, r, value, rv); } vector<int> find_roads(int N, vector<int> u, vector<int> v) { int debug=0; n=N; m=u.size(); forn(i, m){ g[u[i]].PB({v[i], i}); g[v[i]].PB({u[i], i}); edges[i]={u[i], v[i]}; esp[i]=-1; } dfs(0); sort(ted.begin(), ted.end()); base = count_common_roads(ted); uns.resize(ted.size()); forn(i, m){ int a = edges[i].F, b = edges[i].S, know=-1; if(tin[a]<tin[b]) swap(a, b); if(pv[a]==b) continue; uns[lower_bound(ted.begin(), ted.end(), pe[a]) - ted.begin()].PB(i); vector<int> ed, res; int cur=a; while(cur!=b){ int e = pe[cur]; if(esp[e]!=-1) know=e; else{ vector<int> tmp; for(int el:ted) if(el!=e) tmp.PB(el); tmp.PB(i); ed.PB(e); ++debug; res.PB(count_common_roads(tmp)); } cur = pv[cur]; } if(ed.empty()) continue; if(know==-1){ int mx = *max_element(res.begin(), res.end()); mx = max(mx, base); forn(j, ed.size()) esp[ed[j]]=(res[j]!=mx); } else{ vector<int> tmp; for(int el:ted) if(el!=know) tmp.PB(el); tmp.PB(i); ++debug; int value = count_common_roads(tmp); forn(j, ed.size()) esp[ed[j]]=esp[know]^(res[j]!=value); } } assert(debug < 2*n + 5); for(int e:ted) if(esp[e]==-1) esp[e]=1; bool cont=true; while(cont){ int rv = add_count(n-1); dfs2(0, n-1, 0, rv); cont=false; forn(i, n-1){ if(!uns[i].empty()) uns[i].pop_back(); cont|=!uns[i].empty(); } } vector<int> ret; forn(i, m) if(esp[i]==1) ret.PB(i); assert((int)ret.size()==n-1); return ret; }
#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...