Submission #73513

#TimeUsernameProblemLanguageResultExecution timeMemory
73513SmsSSimurgh (IOI17_simurgh)C++14
0 / 100
3 ms616 KiB
#include<bits/stdc++.h> #define pb push_back using namespace std; #define for2(a,b,c) for(int a = b; a < c; a++) #include "simurgh.h" const int maxn = 510; int adj[maxn][maxn]; bool seen[maxn]; bool burn[maxn]; int s[maxn*maxn/2]; int h[maxn]; int par[maxn]; vector<int> res; bool sc = 0; int cur; int n; void dfs(int root){ seen[root] = 1; for2(i,0,n) if(adj[i][root] != -1){ if(!seen[i]){ h[i] = h[root]+1; par[i] = root; if(!sc)res.pb(adj[i][root]); dfs(i); }else if(sc && h[i] > h[root]+1){ int x = i; while(x != root){ int y = par[x]; if(s[adj[x][y]]){ int t = 0; for2(i,0,n-1) if(res[i] == adj[x][y]) t = i; res[t] = adj[i][root]; if(count_common_roads(res) == cur-(s[adj[x][y]]==2)) s[adj[i][root]] = 1; else s[adj[i][root]] = 2; res[t] = adj[x][y]; break; } x = y; } if(!s[adj[i][root]]){ int mx = cur; int mn = cur; vector<int> c; x = i; while(x != root){ int y = par[x]; int t = 0; for2(i,0,n-1) if(res[i] == adj[x][y]) t = i; res[t] = adj[i][root]; c.pb(count_common_roads(res)); mx = max(mx,c.back()); mn = min(mn,c.back()); res[t] = adj[x][y]; x = y; } int cnt = 0; x = i; while(x != root){ int y = par[x]; // cout << x << ' ' << y << endl; if(c[cnt] != mx && mx != mn){ s[adj[x][y]] = 2; }else s[adj[x][y]] = 1; cnt++; x = y; } if(cur != mx && mx != mn){ s[adj[root][i]] = 2; }else s[adj[root][i]] = 1; // for2(i,0,8) cout << s[i] << endl; } } } } //int par[maxn]; int getpar(int x){ if(par[x] < 0) return x; return par[x] = getpar(par[x]); } std::vector<int> find_roads(int N, std::vector<int> u, std::vector<int> v) { int m = u.size(); n = N; for2(i,0,n) for2(j,0,n) adj[i][j] = -1; for2(i,0,m) adj[u[i]][v[i]] = adj[v[i]][u[i]] = i; dfs(0); cur = count_common_roads(res); sc = 1; fill(seen,seen+n,0); dfs(0); fill(par,par+n,-1); vector<int> ans; for2(i,0,m) if(s[i] == 2){ ans.pb(i); int x = getpar(v[i]); int y = getpar(u[i]); if(x == y) continue; par[x] = y; } for(auto e : res){ int x = getpar(v[e]); int y = getpar(u[e]); if(x == y) continue; par[x] = y; res.pb(e); } // for2(i,0,m) cout << s[i] << endl; //for2(i,0,m) if(!s[i]) s[i] = 2; res.clear(); for2(i,0,m) if(s[i] == 2) res.pb(i); return ans; }
#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...