Submission #285601

#TimeUsernameProblemLanguageResultExecution timeMemory
285601mohammadSimurgh (IOI17_simurgh)C++14
51 / 100
339 ms13800 KiB
#include "simurgh.h" #include<bits/stdc++.h> using namespace std; #define endl "\n" // #define int long long typedef long long ll ; const ll ooo = 1e14 ; const ll oo = 2e9 ; const double PI = acos(-1) ; const ll M = 1e9 + 7 ; const int N = 10000010 ; vector<pair<int , int>> g[501]; vector<int> r , ans , p(501) , dp(501 , 0); int sz = 0 ; map<pair<int,int> , int>mp , roy; int root[501]; ll find(int u){ if(root[u] == u) return u ; return root[u] = find(root[u]); } void dfs(int u){ if(p[u] + 1)dp[u] = dp[p[u]] + 1; for(auto v : g[u]) if(v.first != p[u]){ mp[{u , v.first}] = r.size(); mp[{v.first , u}] = r.size(); p[v.first] = u; r.push_back(v.second); dfs(v.first); } } vector<int> find_roads(int n, vector<int> u, vector<int> v) { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); for(int i = 0 ; i < n ; ++i) root[i] = i ; sz = n; int m = u.size(); for(int i = 0 ; i < m ; ++i){ if(find(u[i]) != find(v[i])){ root[find(v[i])] = find(u[i]); g[u[i]].push_back({v[i] , i}); g[v[i]].push_back({u[i] , i}); } mp[{u[i] , v[i]}] = -1; mp[{v[i] , u[i]}] = -1; } dp[0] = 0; dfs(0); int common = count_common_roads(r); for(int i = 0 ; i < m && common != n - 1; ++i){ if(mp[{u[i] , v[i]}] != -1 || roy[{u[i] , v[i]}]) continue ; if(dp[u[i]] > dp[v[i]]) swap(u[i] , v[i]); int x = u[i] , y = v[i]; vector<int> r2 , pz ; int mx = common ; int de = 0; while(dp[y] && mx <= common){ vector<int> r1 = r ; if(dp[y] == dp[x]){ if(x == y) break; if(roy[{x , p[x]}] == 2 && !de){ r1[mp[{x , p[x]}]] = i; int z = count_common_roads(r1); if(z == common) { de = 2; roy[{u[i] , v[i]}] = 2; roy[{v[i] , u[i]}] = 2; break; }else{ de = 1; mx = common + 1; r2 = r1; break; } } x = p[x]; }else if(dp[y] > dp[x]){ if(roy[{y , p[y]}] == 2 && !de){ r1[mp[{y , p[y]}]] = i; int z = count_common_roads(r1); if(z == common) { de = 2; roy[{u[i] , v[i]}] = 2; roy[{v[i] , u[i]}] = 2; break; }else{ de = 1; mx = common + 1; r2 = r1; break; } } y = p[y]; } } // cout << "1=-=--=-=-" << endl; x = u[i] , y = v[i]; while(dp[y] && mx <= common && !de){ vector<int> r1 = r ; if(dp[y] == dp[x]){ if(x == y) break; if(!roy[{x , p[x]}]){ r1[mp[{x , p[x]}]] = i; int z = count_common_roads(r1); pz.push_back(z); if(z < common) { roy[{x , p[x]}] = 1,roy[{p[x] , x}] = 1; break; } if(mx < z){ roy[{x , p[x]}] = 2,roy[{p[x] , x}] = 2; mx = z; r2 = r1; break; } } x = p[x]; }else if(dp[y] > dp[x]){ if(!roy[{y , p[y]}]){ r1[mp[{y , p[y]}]] = i; int z = count_common_roads(r1); pz.push_back(z); if(z < common) { roy[{y , p[y]}] = 1,roy[{p[y] , y}] = 1; break; } if(mx < z){ roy[{y , p[y]}] = 2,roy[{p[y] , y}] = 2; mx = z; r2 = r1; break; } } y = p[y]; } } if(mx > common){ x = u[i] , y = v[i]; int idx = 0; while(dp[y] && !de){ if(dp[y] == dp[x]){ if(x == y) break; if(!roy[{x , p[x]}]){ if(pz[idx] < common)break; else if(common < pz[idx]) break; else roy[{x , p[x]}] = 1; idx++; } x = p[x]; }else if(dp[y] > dp[x]){ if(!roy[{y , p[y]}]){ if(pz[idx] < common)break; else if(common < pz[idx]) break; else roy[{y , p[y]}] = 1; idx++; } y = p[y]; } } roy[{u[i] , v[i]}] = 1; roy[{v[i] , u[i]}] = 1; for(int i = 0 ; i < n; ++i) g[i].clear() , p[i] = 0; for(auto x: r2){ g[u[x]].push_back({v[x] , x}); g[v[x]].push_back({u[x] , x}); } r.clear(); dp[0] = 0; dfs(0); common = mx ; }else{ x = u[i] , y = v[i]; int idx = 0; while(dp[y] && !de){ if(dp[y] == dp[x]){ if(x == y) break; if(!roy[{x , p[x]}]){ if(pz[idx] < common)break; else if(common < pz[idx]) break; else roy[{x , p[x]}] = 2; idx++; } x = p[x]; }else if(dp[y] > dp[x]){ if(!roy[{y , p[y]}]){ if(pz[idx] < common)break; else if(common < pz[idx]) break; else roy[{y , p[y]}] = 2; idx++; } y = p[y]; } } } } return r; }
#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...