제출 #1225289

#제출 시각아이디문제언어결과실행 시간메모리
1225289kokoxuyaNetwork (BOI15_net)C++20
100 / 100
643 ms46952 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define mp make_pair #define pii pair<int,int> #define ss second #define ff first #define piii pair<int,pii> #define debu(x) (cerr << #x << " = "<< x << "\n") #define debu2(x,y) (cerr << #x << " = "<< x << " " << #y << " = " << y << "\n") #define debu3(x,y,z) (cerr << #x << " = "<< x << " " << #y << " = " << y << " " << #z << " = " << z<< "\n") #define bitout(x,y) {\ cerr << #x << " : ";\ for (int justforbits = y; justforbits >=0; justforbits--)cout << (((1 << justforbits) & x)>=1);\ cout << "\n";\ } #define rangeout(j,rangestart,rangeend) {\ cerr << "outputting" << #j<< ":\n";\ for (int forrang = rangestart; forrang <= rangeend; forrang++)cerr << j[forrang] << " ";\ cerr<<"\n";\ } #define c1 {cerr << "Checkpoint 1! \n\n";cerr.flush();} #define c2 {cerr << "Checkpoint 2! \n\n";cerr.flush();} #define c3 {cerr << "Checkpoint 3! \n\n";cerr.flush();} #define c4 {cerr << "Checkpoint 4! \n\n";cerr.flush();} #define defN 500001 vector<vector<int>>adjlist(defN); vector<int>preorder(defN); int curr=0; void dfs(int cn) { preorder[cn]=++curr; for(int to:adjlist[cn]) { if(preorder[to])continue; dfs(to); } } signed main() { int t1,t2,t3,t4; mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count()); //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n;cin>>n; for(int a=1;a<n;a++) { cin>>t1>>t2; adjlist[t2].pb(t1); adjlist[t1].pb(t2); } int myroot; for(int a=1;a<=n;a++) { if(adjlist[a].size()!=1) { myroot=a;break; } } dfs(1); vector<pii>myliz; for(int a=1;a<=n;a++) { if(adjlist[a].size()==1) { myliz.pb(mp(preorder[a],a)); } } sort(myliz.begin(),myliz.end()); cout<<myliz.size()/2+myliz.size()%2<<"\n"; for(int a=0;a<myliz.size()/2;a++) { cout<<myliz[a].ss<<" "<<myliz[a+myliz.size()/2].ss<<"\n"; } if(myliz.size()%2)cout<<myliz[myliz.size()/2].ss<<" "<<myliz[myliz.size()-1].ss<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...