Submission #923242

#TimeUsernameProblemLanguageResultExecution timeMemory
923242byunjaewooSimurgh (IOI17_simurgh)C++17
0 / 100
67 ms4524 KiB
#include "simurgh.h" #include <bits/stdc++.h> using namespace std; const int Nmax=510, Kmax=Nmax*Nmax/2; int N, M, p, par[Nmax], parc[Nmax], dep[Nmax], dfsn[Nmax], top[Nmax], back[Nmax]; int total, chk[Kmax]; vector<pair<int, int>> adj[Nmax], adj2[Nmax]; vector<tuple<int, int, int>> tree; vector<int> V; int value(int x, int y) { // cout<<"value "<<"delete "<<x<<", add "<<y<<"\n"; for(int &i:V) if(i==x) i=y; int ret=count_common_roads(V); for(int &i:V) if(i==y) i=x; return ret; } void DFS(int curr, int prev) { dfsn[curr]=top[curr]=++p; for(auto [next, c]:adj[curr]) if(next!=prev) { if(dfsn[next]) { if(top[curr]>dfsn[next]) top[curr]=dfsn[next], back[curr]=c; } else { par[next]=curr, parc[next]=c, dep[next]=dep[curr]+1; tree.push_back({curr, next, c}); adj2[curr].push_back({next, c}); DFS(next, curr); if(top[curr]>top[next]) top[curr]=top[next], back[curr]=c; } } } void DFS2(int curr) { for(auto [next, c]:adj2[curr]) { DFS2(next); if(chk[c]!=-1) continue; // cout<<curr<<" -> "<<next<<"\n"; if(top[next]>dfsn[curr]) chk[c]=1; else { vector<int> tmp; bool flag=false; int q=0; for(int i=next; dfsn[i]!=top[next]; i=par[i]) { tmp.push_back(parc[i]); if(chk[parc[i]]!=-1) flag=true, q=parc[i]; } /*cout<<"tmp "; for(int i:tmp) cout<<i<<" "; cout<<"\n"; cout<<flag<<", "<<back[next]<<"\n";*/ if(flag) { chk[back[next]]=chk[q]+value(q, back[next])-total; for(int i:tmp) if(chk[i]==-1) chk[i]=chk[back[next]]-value(i, back[next])+total; } else { int X=total; vector<int> Y; for(int i:tmp) Y.push_back(value(i, back[next]));//, cout<<i<<" Y : "<<Y.back()<<"\n"; bool flag2=false; for(int i=0; i<Y.size(); i++) { if(Y[i]==X+1) flag2=true, chk[back[next]]=1, chk[tmp[i]]=0; else if(Y[i]==X-1) flag2=true, chk[back[next]]=0, chk[tmp[i]]=1; } if(flag2) { for(int i=0; i<Y.size(); i++) if(Y[i]==X) chk[tmp[i]]=chk[back[next]]; } else { chk[back[next]]=false; for(int i=0; i<Y.size(); i++) if(Y[i]==X) chk[tmp[i]]=false; } } } } } 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++) { adj[u[i]].push_back({v[i], i}), adj[v[i]].push_back({u[i], i}); } for(int i=0; i<M; i++) chk[i]=-1; DFS(0, -1); /*cout<<"tree:\n"; for(auto [u, v, c]:tree) cout<<u<<", "<<v<<": "<<c<<"\n"; cout<<"\n";*/ for(auto [u, v, c]:tree) V.push_back(c); total=count_common_roads(V); DFS2(0); for(int i=0; i<M; i++) if(chk[i]==-1) { if(dep[u[i]]<dep[v[i]]) swap(u[i], v[i]); chk[i]=chk[parc[u[i]]]-total+value(parc[u[i]], i); } vector<int> ret; for(int i=0; i<M; i++) if(chk[i]) ret.push_back(i); /*cout<<"ret: "; for(int i:ret) cout<<i<<" "; cout<<"\n";*/ return ret; }

Compilation message (stderr)

simurgh.cpp: In function 'void DFS2(int)':
simurgh.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i=0; i<Y.size(); i++) {
      |                  ~^~~~~~~~~
simurgh.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |      for(int i=0; i<Y.size(); i++) if(Y[i]==X) chk[tmp[i]]=chk[back[next]];
      |                   ~^~~~~~~~~
simurgh.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |      for(int i=0; i<Y.size(); i++) if(Y[i]==X) chk[tmp[i]]=false;
      |                   ~^~~~~~~~~
#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...