Submission #137356

#TimeUsernameProblemLanguageResultExecution timeMemory
137356wilwxkSimurgh (IOI17_simurgh)C++14
0 / 100
2 ms376 KiB
#include "simurgh.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=502; int aresta[MAXN*MAXN][2]; vector<int> g[MAXN], gt[MAXN]; int rep[MAXN], tam[MAXN]; vector<int> config; vector<int> respf; bool ruim[MAXN*MAXN]; int n, m; bool debug=0; int find(int cur) { if(rep[cur]==cur) return cur; return rep[cur]=find(rep[cur]); } void une(int a, int b) { a=find(a); b=find(b); if(a==b) return; if(tam[a]<tam[b]) swap(a, b); rep[a]=b; } void geradora() { srand(time(0)+n+m); for(int i=0; i<n; i++) rep[i]=i, tam[i]=i; for(int i=0; i<m; i++) { int a=aresta[i][0]; int b=aresta[i][1]; if(find(a)==find(b)) continue; gt[a].push_back(i); gt[b].push_back(i); une(a, b); if(debug) printf("tree:: %d %d // %d\n", a, b, i); } } int query() { for(int i=0; i<n; i++) rep[i]=i; for(auto cur : config) une(aresta[cur][0], aresta[cur][1]); for(int i=0; i<n; i++) if(find(i)!=find(0)) return MAXN; return count_common_roads(config); } void solve(int cur, int pid) { random_shuffle(g[cur].begin(), g[cur].end()); int ori=query(); vector<int> aux; aux=config; config.clear(); for(auto cur : aux) if(cur!=pid) config.push_back(cur); config.push_back(pid); if(g[cur].size()==1) { respf.push_back(pid); return; } for(auto vid : g[cur]) { if(vid==pid) continue; config.pop_back(); config.push_back(vid); if(debug){for(auto cur : config) printf("%d ", cur); cout << endl;} int val=query(); config.pop_back(); config.push_back(pid); if(val!=ori) { if(val<ori) respf.push_back(pid); else respf.push_back(vid); break; } } } void predfs(int cur, int pid) { if(pid!=-1) config.push_back(pid); for(auto vid : gt[cur]) { if(vid==pid) continue; int viz= aresta[vid][aresta[vid][0]==cur]; predfs(viz, vid); } if(pid==-1) return; } void dfs(int cur, int pid) { if(debug) printf("%d %d\n", cur, pid); for(auto vid : gt[cur]) { if(vid==pid) continue; int viz= aresta[vid][aresta[vid][0]==cur]; dfs(viz, vid); } if(pid==-1) return; solve(cur, pid); } std::vector<int> find_roads(int N, std::vector<int> U, std::vector<int> V) { n=N; m=U.size(); for(int i=0; i<m; i++) { int a=U[i]; int b=V[i]; aresta[i][0]=a; aresta[i][1]=b; g[a].push_back(i); g[b].push_back(i); } geradora(); predfs(0, -1); dfs(0, -1); return respf; }
#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...