Submission #1100502

#TimeUsernameProblemLanguageResultExecution timeMemory
1100502MMihalevSimurgh (IOI17_simurgh)C++14
51 / 100
95 ms4280 KiB
#include<iostream> #include<algorithm> #include<set> #include<queue> #include "simurgh.h" using namespace std; const int MAX_N=5e2+3; const int MAX_M=125000; int n,m; int q; vector<int>edges; vector<pair<int,int>>g[MAX_N]; bool used[MAX_N]; vector<int>comp; vector<vector<int>>comps; int adj[MAX_N]; int numedge[MAX_N][MAX_N]; bool stat[MAX_M]; bool checked[MAX_M]; int forsure; void reset() { comps.clear(); edges.clear(); for(int i=0;i<n;i++) { adj[i]=-1; used[i]=0; } } void dfs(int u) { if(adj[u]!=-1) { if(!checked[adj[u]]) { comp.push_back(adj[u]); } if(stat[adj[u]])forsure=adj[u]; } used[u]=1; for(auto [v,edge]:g[u]) { if(used[v])continue; edges.push_back(edge); dfs(v); } } void rep(int prev,int edge) { for(int i=0;i<edges.size();i++) { if(edges[i]==prev){edges[i]=edge;return;} } } vector<pair<int,int>>s; int rec(int l,int r) { if(l==r) { return s[l].first; } int mid=(l+r)/2; int bonus=0; edges.clear(); for(int i=0;i<n;i++)used[i]=0; for(int i=l;i<=mid;i++) { edges.push_back(s[i].first); used[s[i].second]=1; } for(int i=1;i<n;i++) { if(!used[i]){bonus+=stat[numedge[0][i]];edges.push_back(numedge[0][i]);} } int cnt=count_common_roads(edges)-bonus; if(cnt>0)return rec(l,mid); return rec(mid+1,r); } vector<int> find_roads(int N, vector<int> u, vector<int> v) { n=N; m=u.size(); vector<int>ans; for(int i=0;i<m;i++) { g[u[i]].push_back({v[i],i}); g[v[i]].push_back({u[i],i}); numedge[u[i]][v[i]]=i; numedge[v[i]][u[i]]=i; } if(n<=240) { for(int u=0;u<n;u++) { reset(); used[u]=1; for(auto [v,edge]:g[u]) { adj[v]=edge; } for(auto [v,edge]:g[u]) { if(!used[v]) { forsure=-1; comp.clear(); dfs(v); if(forsure!=-1) { comp.push_back(forsure); } comps.push_back(comp); } } for(auto c:comps) { edges.push_back(c[0]); } for(auto c:comps) { int ma=count_common_roads(edges);q++; vector<int>marked; marked.push_back(c[0]); int prev=c[0]; int sega=0; for(int edge:c) { if(edge==c[0])continue; rep(prev,edge); int cur=count_common_roads(edges);q++; if(cur>ma) { sega++; marked.clear(); ma=cur; marked.push_back(edge); if(sega==2)break; } else if(cur==ma) { marked.push_back(edge); } prev=edge; } for(int edge:marked)stat[edge]=1; } for(auto [v,edge]:g[u])checked[edge]=1; } } else { for(int u=0;u<n;u++) { if(u==0) { vector<int>marked; edges.clear(); for(int v=2;v<n;v++) { edges.push_back(numedge[v-1][v]); } int ma=-1; for(auto [v,edge]:g[u]) { edges.push_back(edge); int cur=count_common_roads(edges); if(cur>ma) { marked.clear(); marked.push_back(edge); ma=cur; } else if(cur==ma)marked.push_back(edge); } for(int edge:marked)stat[edge]=1; continue; } while(1) { int bonus=0; edges.clear(); s.clear(); for(int i=0;i<n;i++)used[i]=0; for(auto [v,edge]:g[u]) { if(stat[edge] or v==0)continue; edges.push_back(edge); s.push_back({edge,v}); used[v]=1; } for(int i=1;i<n;i++) { if(!used[i]){bonus+=stat[numedge[0][i]];edges.push_back(numedge[0][i]);} } int cur=count_common_roads(edges)-bonus; if(cur==0)break; int edge=rec(0,s.size()-1); stat[edge]=1; } } } for(int i=0;i<m;i++) { if(stat[i])ans.push_back(i); } if(ans.size()!=n-1)while(1); return ans; }

Compilation message (stderr)

simurgh.cpp: In function 'void dfs(int)':
simurgh.cpp:44:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |     for(auto [v,edge]:g[u])
      |              ^
simurgh.cpp: In function 'void rep(int, int)':
simurgh.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=0;i<edges.size();i++)
      |                 ~^~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:108:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  108 |             for(auto [v,edge]:g[u])
      |                      ^
simurgh.cpp:112:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  112 |             for(auto [v,edge]:g[u])
      |                      ^
simurgh.cpp:166:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  166 |             for(auto [v,edge]:g[u])checked[edge]=1;
      |                      ^
simurgh.cpp:185:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  185 |                 for(auto [v,edge]:g[u])
      |                          ^
simurgh.cpp:212:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  212 |                 for(auto [v,edge]:g[u])
      |                          ^
simurgh.cpp:240:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  240 |     if(ans.size()!=n-1)while(1);
      |        ~~~~~~~~~~^~~~~
#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...