# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
410330 | 2021-05-22T14:04:08 Z | Antekb | Simurgh (IOI17_simurgh) | C++14 | 1 ms | 204 KB |
#include "simurgh.h" #include<bits/stdc++.h> using namespace std; int n; vector<int> U, V; map<vector<int>, int> M; int count(vector<int> v){ //cout<<v.size()<<"\n"; assert(v.size()==n-1); sort(v.begin(), v.end()); if(M.find(v)==M.end()) M[v]=count_common_roads(v); return M[v]; } vector<int> R; int find(int v){ if(v==R[v])return v; return R[v]=find(R[v]); } void Union(int u, int v){ R[u]=v; } int spe; vector<int> V2[505]; vector<int> span(vector<int> &kol){ R.resize(n); iota(R.begin(), R.end(), 0); vector<int> ans; for(int i:kol){ //cout<<U[i]<<" "<<V[i]<<endl; int u=find(U[i]), v=find(V[i]); if(U[i]==spe)V2[v].push_back(i); else if(V[i]==spe)V2[u].push_back(i); else if(u!=v){ Union(u, v); ans.push_back(i); } } return ans; } vector<int> dobre; std::vector<int> find_roads(int _n, std::vector<int> u2, std::vector<int> v2) { U=u2; V=v2; n=_n; int m=U.size(); vector<int> edg(m); iota(edg.begin(), edg.end(), 0); for(int i=0; i<n; i++){ int k=edg.size()-1; for(int j=0; j<k; j++){ if(U[edg[j]]==i || V[edg[j]]==i){ while(k>=0 && (U[edg[k]]==i || V[edg[k]]==i))k--; if(j>k)break; swap(edg[j], edg[k]); } } spe=i; for(int j=0; j<n; j++)V2[j].clear(); vector<int> tre=span(edg); /*bool b=1; for(int j=0; j<tre.size()-1; j++){ if((U[tre[j]]==i || V[tre[j]]==i)){ swap(tre[j], tre.back()); } } for(int j=0; j<tre.size()-1; j++){ if((U[tre[j]]==i || V[tre[j]]==i)){ b=0; } } if(b){*/ //cout<<i<<" a"<<endl; vector<int> gdzie; for(int j=0; j<n; j++){ if(V2[j].size()){ //cout<<"b"; gdzie.push_back(j); tre.push_back(V2[j].back()); } } //cout<<tre.size()<<"\n"; for(int k=0; k<gdzie.size(); k++){ vector<int> ans; int M=0; //cout<<tre[0]<<" "<<tre[1]<<" "<<tre[2]<<" "<<tre[3]<<" b\n"; for(int j:V2[gdzie[k]]){ //cout<<n-1-k<<"\n"; if(U[j]==i || V[j]==i){ tre[n-2-k]=j; //cout<<tre[0]<<" "<<tre[1]<<" "<<tre[2]<<"\n"; ans.push_back(count(tre)); M=max(M, ans.back()); //cout<<j<<" "<<ans.back()<<"\n"; } } int cnt=0; deque<int> todo; for(int j:V2[gdzie[k]]){ //if(U[edg[j]]==i || V[edg[j]]==i){ if(ans[cnt]<M){ todo.push_back(j); //cout<<todo.back()<<"q "; } cnt++; //} } vector<int> edg2; for(int j=0; j<edg.size(); j++){ if(todo.size() && edg[j]==todo.front()){ todo.pop_front(); } else edg2.push_back(edg[j]); } edg=edg2; //cout<<"\n"; } } //for(int j:edg)cout<<j<<" "; assert(edg.size()==n-1); assert(count(edg)==n-1); sort(edg.begin(), edg.end()); return edg; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 204 KB | WA in grader: NO |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 204 KB | WA in grader: NO |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 204 KB | WA in grader: NO |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | correct |
2 | Incorrect | 1 ms | 204 KB | WA in grader: NO |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 204 KB | WA in grader: NO |
2 | Halted | 0 ms | 0 KB | - |