# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
22987 | 2017-05-01T02:49:34 Z | model_code | Network (BOI15_net) | C++11 | 2000 ms | 20220 KB |
/*/ Task: net Brute-force solution With early termination With O(n) bridge finding Author: Bartosz Kostka /*/ #include "bits/stdc++.h" using namespace std; const int MAXN = 500007; vector <int> L, G[MAXN]; int w, n; int licz; int d[MAXN+7], low[MAXN+7], par[MAXN+7]; bool vis[MAXN+7]; void dfs(int v) { vis[v] = 1; for(auto w : G[v]) { if(vis[w] == false) { par[w] = v; d[w] = d[v] + 1; dfs(w); } } low[v] = d[v]; bool multiple = false; for(auto w : G[v]) { //jest moim synem if(par[w] == v) { low[v] = min(low[v], low[w]); continue; } //jest moim ojcem if(w == par[v] and multiple == false) { multiple = true; continue; } //jest krawedzia wtorna low[v] = min(low[v], d[w]); } } bool bridges() { for(int i=1; i<=n; i++) vis[i] = false; for(int i=1; i<=n; i++) low[i] = par[i] = d[i] = 0; dfs(1); for(int i=1; i<=n; i++) if(d[i]==low[i] and d[i]) return true; return false; } void print(vector <int> &S) { printf("%d\n", (int)S.size()/2); for(int i=0; i<(int)S.size(); i+=2) printf("%d %d\n", S[i], S[i+1]); exit(0); } void go(vector <int> &L, vector <int> &A) { if(L.size() <= 1) { if(!L.empty()) { G[L[0]].push_back(w); G[w].push_back(L[0]); A.push_back(L[0]); A.push_back(w); if(bridges()==false) print(A); A.pop_back(); A.pop_back(); G[w].pop_back(); G[L[0]].pop_back(); } else { if(bridges()==false) print(A); } return; } int a = L.back(); L.pop_back(); int ls = (int)L.size(); A.push_back(a); for(int i=0; i<ls; i++) { swap(L[i], L.back()); int b = L.back(); L.pop_back(); G[a].push_back(b); G[b].push_back(a); A.push_back(b); go(L,A); A.pop_back(); G[b].pop_back(); G[a].pop_back(); L.push_back(b); swap(L[i], L.back()); } A.pop_back(); L.push_back(a); } int main() { scanf("%d", &n); for(int i=1; i<n; i++) { int a, b; scanf("%d%d", &a, &b); G[a].push_back(b); G[b].push_back(a); } for(int i=1; i<=n; i++) { if((int)G[i].size() == 1) L.push_back(i); else w = i; } vector <int> AA; go(L,AA); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 20088 KB | Output is correct |
2 | Correct | 0 ms | 20088 KB | Output is correct |
3 | Correct | 3 ms | 20088 KB | Output is correct |
4 | Correct | 0 ms | 20088 KB | Output is correct |
5 | Correct | 3 ms | 20088 KB | Output is correct |
6 | Correct | 6 ms | 20088 KB | Output is correct |
7 | Correct | 0 ms | 20088 KB | Output is correct |
8 | Correct | 3 ms | 20088 KB | Output is correct |
9 | Correct | 3 ms | 20088 KB | Output is correct |
10 | Correct | 3 ms | 20088 KB | Output is correct |
11 | Correct | 6 ms | 20088 KB | Output is correct |
12 | Correct | 0 ms | 20088 KB | Output is correct |
13 | Correct | 3 ms | 20088 KB | Output is correct |
14 | Correct | 6 ms | 20088 KB | Output is correct |
15 | Correct | 3 ms | 20088 KB | Output is correct |
16 | Correct | 0 ms | 20088 KB | Output is correct |
17 | Correct | 0 ms | 20088 KB | Output is correct |
18 | Correct | 0 ms | 20088 KB | Output is correct |
19 | Correct | 0 ms | 20088 KB | Output is correct |
20 | Correct | 6 ms | 20088 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 20088 KB | Output is correct |
2 | Correct | 0 ms | 20088 KB | Output is correct |
3 | Correct | 3 ms | 20088 KB | Output is correct |
4 | Correct | 0 ms | 20088 KB | Output is correct |
5 | Correct | 3 ms | 20088 KB | Output is correct |
6 | Correct | 6 ms | 20088 KB | Output is correct |
7 | Correct | 0 ms | 20088 KB | Output is correct |
8 | Correct | 3 ms | 20088 KB | Output is correct |
9 | Correct | 3 ms | 20088 KB | Output is correct |
10 | Correct | 3 ms | 20088 KB | Output is correct |
11 | Correct | 6 ms | 20088 KB | Output is correct |
12 | Correct | 0 ms | 20088 KB | Output is correct |
13 | Correct | 3 ms | 20088 KB | Output is correct |
14 | Correct | 6 ms | 20088 KB | Output is correct |
15 | Correct | 3 ms | 20088 KB | Output is correct |
16 | Correct | 0 ms | 20088 KB | Output is correct |
17 | Correct | 0 ms | 20088 KB | Output is correct |
18 | Correct | 0 ms | 20088 KB | Output is correct |
19 | Correct | 0 ms | 20088 KB | Output is correct |
20 | Correct | 6 ms | 20088 KB | Output is correct |
21 | Correct | 6 ms | 20088 KB | Output is correct |
22 | Correct | 0 ms | 20220 KB | Output is correct |
23 | Correct | 6 ms | 20220 KB | Output is correct |
24 | Correct | 6 ms | 20220 KB | Output is correct |
25 | Correct | 3 ms | 20220 KB | Output is correct |
26 | Correct | 3 ms | 20220 KB | Output is correct |
27 | Correct | 0 ms | 20220 KB | Output is correct |
28 | Execution timed out | 2000 ms | 20220 KB | Execution timed out |
29 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 20088 KB | Output is correct |
2 | Correct | 0 ms | 20088 KB | Output is correct |
3 | Correct | 3 ms | 20088 KB | Output is correct |
4 | Correct | 0 ms | 20088 KB | Output is correct |
5 | Correct | 3 ms | 20088 KB | Output is correct |
6 | Correct | 6 ms | 20088 KB | Output is correct |
7 | Correct | 0 ms | 20088 KB | Output is correct |
8 | Correct | 3 ms | 20088 KB | Output is correct |
9 | Correct | 3 ms | 20088 KB | Output is correct |
10 | Correct | 3 ms | 20088 KB | Output is correct |
11 | Correct | 6 ms | 20088 KB | Output is correct |
12 | Correct | 0 ms | 20088 KB | Output is correct |
13 | Correct | 3 ms | 20088 KB | Output is correct |
14 | Correct | 6 ms | 20088 KB | Output is correct |
15 | Correct | 3 ms | 20088 KB | Output is correct |
16 | Correct | 0 ms | 20088 KB | Output is correct |
17 | Correct | 0 ms | 20088 KB | Output is correct |
18 | Correct | 0 ms | 20088 KB | Output is correct |
19 | Correct | 0 ms | 20088 KB | Output is correct |
20 | Correct | 6 ms | 20088 KB | Output is correct |
21 | Correct | 6 ms | 20088 KB | Output is correct |
22 | Correct | 0 ms | 20220 KB | Output is correct |
23 | Correct | 6 ms | 20220 KB | Output is correct |
24 | Correct | 6 ms | 20220 KB | Output is correct |
25 | Correct | 3 ms | 20220 KB | Output is correct |
26 | Correct | 3 ms | 20220 KB | Output is correct |
27 | Correct | 0 ms | 20220 KB | Output is correct |
28 | Execution timed out | 2000 ms | 20220 KB | Execution timed out |
29 | Halted | 0 ms | 0 KB | - |