제출 #1091617

#제출 시각아이디문제언어결과실행 시간메모리
1091617DeathIsAweNetwork (BOI15_net)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; bool visited[500000]; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, d1,d2; cin >> n; vector<vector<int>> graph(n); for (int i=0;i<n-1;i++) { cin >> d1 >> d2; d1--; d2--; graph[d1].push_back(d2); graph[d2].push_back(d1); visited[i] = false; } visited[n - 1] = false; vector<int> leaves; stack<int> dfs; dfs.push(0); int node; bool flag; while (dfs.size() > 0) { flag = false; node = dfs.top(); dfs.pop(); visited[node] = true; for (int i: graph[node]) { if (!visited[i]) { dfs.push(i); flag = true; } } if (!flag) { leaves.push_back(node); } } int m = leaves.size(); cout << (m + 1) / 2 << '\n'; for (int i=0;i<m/2;i++) { cout << leaves[i] + 1 << ' ' << leaves[i + (m / 2)] + 1 << '\n'; } if (m % 2 == 1) { cout << leaves[m - 1] + 1 << ' ' << leaves[m - 1 - (m / 2)] + 1 ; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...