# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
650803 | 2022-10-15T11:51:57 Z | groshi | Senior Postmen (BOI14_postmen) | C++17 | 400 ms | 83452 KB |
#include<iostream> #include<vector> #include<utility> #include<unordered_map> #include<set> using namespace std; int byla[1000000]; int odw[1000000]; set<pair<int,int> > secik; struct wi{ vector<pair<int,int> > Q; int odw=0; int wyszlam=0; }*w; vector<int> stos,wynik; int kiedy=1; int wzielam=0; int dokad=0; bool czy[1000000]; void dfs(int x,int ojc) { //cout<<x<<" "<<ojc<<"\n"; stos.push_back(x); w[x].odw=kiedy; for(int i=0;i<w[x].Q.size();i++) { //cout<<"zdycham\n"; int pom=w[x].Q[i].first; int ktora=w[x].Q[i].second; while(czy[ktora]==1) { swap(w[x].Q[i],w[x].Q.back()); w[x].Q.pop_back(); if(i>=w[x].Q.size()) break; pom=w[x].Q[i].first; ktora=w[x].Q[i].second; } //cout<<"zdycham 2\n"; if(i>=w[x].Q.size()) break; if(pom==ojc) continue; if(w[pom].odw==kiedy && w[pom].wyszlam==kiedy) continue; if(w[pom].odw!=kiedy) { dfs(pom,x); if(dokad==0) continue; czy[ktora]=1; cout<<stos.back()<<" "; if(dokad!=x) stos.pop_back(); if(dokad==x) { cout<<"\n"; dokad=0; //cout<<"tako\n"; continue; } w[x].wyszlam=kiedy; //cout<<"wychodze z "<<x<<"\n"; return; } //cout<<"bede chciec znalezc cykl od "<<x<<" do "<<pom<<"\n"; czy[ktora]=1; cout<<stos.back()<<" "; dokad=pom; stos.pop_back(); w[x].wyszlam=kiedy; //cout<<"umieram\n"; return; } w[x].wyszlam=kiedy; stos.pop_back(); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m,x,y; cin>>n>>m; w=new wi[n+3]; for(int i=0;i<m;i++) { cin>>x>>y; w[x].Q.push_back({y,i}); w[y].Q.push_back({x,i}); } for(int i=1;i<=n;i++) { kiedy++; dfs(i,0); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 336 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 2 ms | 468 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 4 ms | 476 KB | Output is correct |
7 | Correct | 6 ms | 980 KB | Output is correct |
8 | Correct | 2 ms | 596 KB | Output is correct |
9 | Correct | 32 ms | 3556 KB | Output is correct |
10 | Correct | 2 ms | 468 KB | Output is correct |
11 | Correct | 2 ms | 468 KB | Output is correct |
12 | Correct | 34 ms | 3992 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 2 ms | 468 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 2 ms | 412 KB | Output is correct |
7 | Correct | 6 ms | 980 KB | Output is correct |
8 | Correct | 1 ms | 596 KB | Output is correct |
9 | Correct | 33 ms | 3536 KB | Output is correct |
10 | Correct | 2 ms | 468 KB | Output is correct |
11 | Correct | 2 ms | 488 KB | Output is correct |
12 | Correct | 34 ms | 4044 KB | Output is correct |
13 | Correct | 61 ms | 16736 KB | Output is correct |
14 | Correct | 51 ms | 7372 KB | Output is correct |
15 | Correct | 39 ms | 6464 KB | Output is correct |
16 | Correct | 62 ms | 16680 KB | Output is correct |
17 | Correct | 46 ms | 6888 KB | Output is correct |
18 | Correct | 47 ms | 9528 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 2 ms | 468 KB | Output is correct |
5 | Correct | 1 ms | 344 KB | Output is correct |
6 | Correct | 2 ms | 468 KB | Output is correct |
7 | Correct | 5 ms | 980 KB | Output is correct |
8 | Correct | 2 ms | 596 KB | Output is correct |
9 | Correct | 36 ms | 3484 KB | Output is correct |
10 | Correct | 2 ms | 484 KB | Output is correct |
11 | Correct | 1 ms | 484 KB | Output is correct |
12 | Correct | 35 ms | 4040 KB | Output is correct |
13 | Correct | 66 ms | 16664 KB | Output is correct |
14 | Correct | 70 ms | 7404 KB | Output is correct |
15 | Correct | 43 ms | 6464 KB | Output is correct |
16 | Correct | 66 ms | 16744 KB | Output is correct |
17 | Correct | 50 ms | 6904 KB | Output is correct |
18 | Correct | 74 ms | 9476 KB | Output is correct |
19 | Correct | 367 ms | 83360 KB | Output is correct |
20 | Correct | 348 ms | 36904 KB | Output is correct |
21 | Correct | 325 ms | 32000 KB | Output is correct |
22 | Correct | 400 ms | 83452 KB | Output is correct |
23 | Correct | 186 ms | 15360 KB | Output is correct |
24 | Correct | 394 ms | 34636 KB | Output is correct |
25 | Correct | 400 ms | 47224 KB | Output is correct |