# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
129763 | 2019-07-13T07:32:35 Z | Vardanyan | 어르신 집배원 (BOI14_postmen) | C++14 | 500 ms | 133540 KB |
#include <bits/stdc++.h> using namespace std; const int N = 500*1000+5; vector<int> g[N]; vector<int> hv[N]; vector<int> pos[N]; vector<int> ans; int st; bool col[N]; vector<vector<int> > all; int POS[N]; void dfs (int v, int p = -1) { //printf("%d!\n", v); if (col[v]) { st = v; //ans.clear(); ans.push_back(v); return; } col[v] = 1; // set<int>::iterator it = g[v].begin(); for(int i = POS[v];i<g[v].size();i++){ int to = g[v][i]; if (to != p && hv[v][i]) { dfs(to, v); // g[v].erase(g[v].find(to)); //g[to].erase(g[to].find(v)); //mp[v][to] = mp[to][v] = 0; hv[v][i] = 0; hv[to][pos[v][i]] = 0; POS[v]++; if (v != st) { ans.push_back(v); break; } else { all.push_back(ans); ans.clear(); //return; } } } col[v] = 0; } int main(){ // ios_base::sync_with_stdio(false); int n,m; scanf("%d%d",&n,&m); for(int i = 0;i<m;i++){ int x,y; scanf("%d%d",&x,&y); g[x].push_back(y); g[y].push_back(x); //mp[x][y] = 1; // mp[y][x] = 1; hv[x].push_back(1); hv[y].push_back(1); pos[x].push_back(g[y].size()-1); pos[y].push_back(g[x].size()-1); } // cout<<endl; vector<int> v; for(int i = 1;i<=n;i++) v.push_back(i); // random_shuffle(v.begin(),v.end()); for(int j = 0;j<n;j++){ int i = v[j]; /*if(i == 2){ cout<<0<<endl; }*/ /* num++; now.clear(); ans.clear(); now.push_back(i);*/ dfs(i); /*if(!ans.size()) continue; for(int i = 0;i<ans.size()-1;i++){ cout<<ans[i]<<" "; int x = ans[i]; int y = ans[i+1]; g[x].erase(g[x].find(y)); g[y].erase(g[y].find(x)); }*/ // cout<<endl; } for(int i = 0;i<all.size();i++){ if(!all[i].size()) continue; for(int j = 0;j<all[i].size();j++) printf("%d ",all[i][j]); printf("\n"); } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 28 ms | 35560 KB | Output is correct |
2 | Correct | 25 ms | 35584 KB | Output is correct |
3 | Correct | 27 ms | 35584 KB | Output is correct |
4 | Correct | 28 ms | 35840 KB | Output is correct |
5 | Correct | 24 ms | 35584 KB | Output is correct |
6 | Correct | 28 ms | 35840 KB | Output is correct |
7 | Correct | 33 ms | 36352 KB | Output is correct |
8 | Correct | 31 ms | 35960 KB | Output is correct |
9 | Correct | 101 ms | 39288 KB | Output is correct |
10 | Correct | 28 ms | 35840 KB | Output is correct |
11 | Correct | 32 ms | 35840 KB | Output is correct |
12 | Correct | 101 ms | 39892 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 25 ms | 35560 KB | Output is correct |
2 | Correct | 25 ms | 35576 KB | Output is correct |
3 | Correct | 24 ms | 35584 KB | Output is correct |
4 | Correct | 30 ms | 35892 KB | Output is correct |
5 | Correct | 30 ms | 35560 KB | Output is correct |
6 | Correct | 26 ms | 35712 KB | Output is correct |
7 | Correct | 37 ms | 36344 KB | Output is correct |
8 | Correct | 32 ms | 35944 KB | Output is correct |
9 | Correct | 92 ms | 39288 KB | Output is correct |
10 | Correct | 28 ms | 35856 KB | Output is correct |
11 | Correct | 28 ms | 35840 KB | Output is correct |
12 | Correct | 91 ms | 39776 KB | Output is correct |
13 | Correct | 204 ms | 55152 KB | Output is correct |
14 | Correct | 190 ms | 45412 KB | Output is correct |
15 | Correct | 179 ms | 45764 KB | Output is correct |
16 | Correct | 217 ms | 55152 KB | Output is correct |
17 | Correct | 194 ms | 45556 KB | Output is correct |
18 | Correct | 194 ms | 47608 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 30 ms | 35584 KB | Output is correct |
2 | Correct | 23 ms | 35600 KB | Output is correct |
3 | Correct | 25 ms | 35560 KB | Output is correct |
4 | Correct | 26 ms | 35840 KB | Output is correct |
5 | Correct | 26 ms | 35636 KB | Output is correct |
6 | Correct | 27 ms | 35832 KB | Output is correct |
7 | Correct | 31 ms | 36352 KB | Output is correct |
8 | Correct | 26 ms | 35968 KB | Output is correct |
9 | Correct | 86 ms | 39288 KB | Output is correct |
10 | Correct | 28 ms | 35888 KB | Output is correct |
11 | Correct | 32 ms | 35840 KB | Output is correct |
12 | Correct | 97 ms | 39776 KB | Output is correct |
13 | Correct | 214 ms | 55268 KB | Output is correct |
14 | Correct | 172 ms | 45268 KB | Output is correct |
15 | Correct | 169 ms | 45824 KB | Output is correct |
16 | Correct | 200 ms | 55152 KB | Output is correct |
17 | Correct | 202 ms | 45676 KB | Output is correct |
18 | Correct | 215 ms | 47500 KB | Output is correct |
19 | Execution timed out | 1036 ms | 133540 KB | Time limit exceeded |
20 | Halted | 0 ms | 0 KB | - |