제출 #79556

#제출 시각아이디문제언어결과실행 시간메모리
79556VinhspmNetwork (BOI15_net)C++14
0 / 100
26 ms24056 KiB
#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back typedef pair<int, int> ii; const int N = 5e5 + 10; const int oo = 1e9; int n; int deg[N], sz[N]; bool visit[N]; vector<int> lef, rig, vi[N]; void dfs(int pre, int u) { sz[u] = 1; for(int v: vi[u]) if(v != pre) dfs(u, v), sz[u] += sz[v]; // :D } void findcen(int pre, int u, int sz1, bool spm) { if(spm) visit[u] = true; if(!spm) { for(int v: vi[u]) if(v != pre && sz[v] * 2 >= sz1) { findcen(u, v, sz1, 0); return; } } visit[u] = true; for(int v: vi[u]) if(v != pre) findcen(u, v, sz1, 1); } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int i = 1; i < n; ++i) { int u, v; cin >> u >> v; vi[u].pb(v); vi[v].pb(u); deg[u] ++; deg[v] ++; } int ans = 0; for(int i = 1; i <= n; ++i) if(deg[i] == 1) ans ++; dfs(1, 1); findcen(1, 1, sz[1], 0); for(int i = 1; i <= n; ++i) if(deg[i] ==1) { if(!visit[i]) lef.pb(i); else rig.pb(i); } cout << (ans + 1) / 2 << '\n'; int ptr1 = 0, ptr2 = 0; while(ptr1 < lef.size() && ptr2 < rig.size()) { cout << lef[ptr1] << ' ' << rig[ptr2] << '\n'; ptr1 ++; ptr2 ++; } while(ptr1 < lef.size() - 1) cout << lef[ptr1] << ' ' << lef[ptr1 + 1] << '\n' , ptr1 += 2; if(ptr1 < lef.size()) cout << lef[ptr1] << ' ' << rig[0] << '\n'; while(ptr2 < rig.size() - 1) cout << rig[ptr2] << ' ' << rig[ptr2 + 1] << '\n' , ptr2 += 2; if(ptr2 < rig.size()) cout << rig[ptr2] << ' ' << lef[0] << '\n'; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

net.cpp: In function 'int main()':
net.cpp:57:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ptr1 < lef.size() && ptr2 < rig.size()) {
           ~~~~~^~~~~~~~~~~~
net.cpp:57:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ptr1 < lef.size() && ptr2 < rig.size()) {
                                ~~~~~^~~~~~~~~~~~
net.cpp:61:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ptr1 < lef.size() - 1) cout << lef[ptr1] << ' ' << lef[ptr1 + 1] << '\n' , ptr1 += 2;
           ~~~~~^~~~~~~~~~~~~~~~
net.cpp:62:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(ptr1 < lef.size()) cout << lef[ptr1] << ' ' << rig[0] << '\n';
        ~~~~~^~~~~~~~~~~~
net.cpp:63:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ptr2 < rig.size() - 1) cout << rig[ptr2] << ' ' << rig[ptr2 + 1] << '\n' , ptr2 += 2;
           ~~~~~^~~~~~~~~~~~~~~~
net.cpp:64:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(ptr2 < rig.size()) cout << rig[ptr2] << ' ' << lef[0] << '\n';
        ~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...