# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
821787 | 2023-08-11T16:35:04 Z | exodus_ | Network (BOI15_net) | C++14 | 7 ms | 12116 KB |
#include<bits/stdc++.h> #define fi first #define se second using namespace std; const int nmax = 500005; vector<int>adj[nmax]; bool leaf[nmax]={0}; bool vis[nmax]={0}; vector<pair<int,int>>dist; vector<pair<int,int>>daft; void dfs(int x) { stack<pair<int,int>>st; st.push({x,1}); while(!st.empty()) { int nod = st.top().fi; int dis = st.top().se; vis[nod]=true; if(leaf[nod]) { dist.push_back({dis,nod}); } st.pop(); for(auto it:adj[nod]) { if(vis[it]==false) { st.push({it, dis+1}); } } } return; } int main() { int n,a,b; cin >> n; for(int i=1; i<n; i++) { cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } int randomleaf; for(int i=1; i<=n; i++) { if(adj[i].size()==1) { leaf[i]=true; randomleaf=i; } } dfs(randomleaf); sort(dist.begin(), dist.end()); int mid = dist.size()/2; if(dist.size()%2==1) { int j=mid+1; for(int i=0; i<dist.size()/2; i++) { daft.push_back({dist[i].se, dist[j].se}); j++; } daft.push_back({dist[mid].se,dist[0].se}); } else { int j = mid; for(int i=0; i<dist.size()/2; i++) { daft.push_back({dist[i].se, dist[j].se}); j++; } } cout << daft.size() << endl; for(int i=0; i<daft.size(); i++) { cout << daft[i].fi << " " << daft[i].se << endl; } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 12052 KB | Output is correct |
2 | Correct | 5 ms | 11988 KB | Output is correct |
3 | Correct | 5 ms | 12048 KB | Output is correct |
4 | Correct | 6 ms | 12116 KB | Output is correct |
5 | Correct | 6 ms | 11988 KB | Output is correct |
6 | Correct | 5 ms | 11988 KB | Output is correct |
7 | Correct | 6 ms | 11988 KB | Output is correct |
8 | Correct | 5 ms | 11988 KB | Output is correct |
9 | Correct | 6 ms | 11988 KB | Output is correct |
10 | Incorrect | 6 ms | 11988 KB | Breaking single line is causing network to disconnect. |
11 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 12052 KB | Output is correct |
2 | Correct | 5 ms | 11988 KB | Output is correct |
3 | Correct | 5 ms | 12048 KB | Output is correct |
4 | Correct | 6 ms | 12116 KB | Output is correct |
5 | Correct | 6 ms | 11988 KB | Output is correct |
6 | Correct | 5 ms | 11988 KB | Output is correct |
7 | Correct | 6 ms | 11988 KB | Output is correct |
8 | Correct | 5 ms | 11988 KB | Output is correct |
9 | Correct | 6 ms | 11988 KB | Output is correct |
10 | Incorrect | 6 ms | 11988 KB | Breaking single line is causing network to disconnect. |
11 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 12052 KB | Output is correct |
2 | Correct | 5 ms | 11988 KB | Output is correct |
3 | Correct | 5 ms | 12048 KB | Output is correct |
4 | Correct | 6 ms | 12116 KB | Output is correct |
5 | Correct | 6 ms | 11988 KB | Output is correct |
6 | Correct | 5 ms | 11988 KB | Output is correct |
7 | Correct | 6 ms | 11988 KB | Output is correct |
8 | Correct | 5 ms | 11988 KB | Output is correct |
9 | Correct | 6 ms | 11988 KB | Output is correct |
10 | Incorrect | 6 ms | 11988 KB | Breaking single line is causing network to disconnect. |
11 | Halted | 0 ms | 0 KB | - |