| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 284006 |
2020-08-26T11:48:49 Z |
aloo123 |
Network (BOI15_net) |
C++14 |
|
9 ms |
12032 KB |
#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstring>
#include <chrono>
#include <complex>
#define endl "\n"
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 1000000000000000001;
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define pb push_back
#define f first
#define s second
#define pi 3.141592653589793238
using namespace std;
ll gcd( ll a, ll b )
{
if(b==0)
{
return a;
}
else
{
return gcd( b, a%b );
}
}
ll lcm (ll a, ll b)
{
return (a*b)/gcd(a,b);
}
ll power(ll a, ll b) //a is base, b is exponent
{
if(b==0)
return 1;
if(b==1)
return a;
if(b%2 == 1)
return (power(a,b-1)*a)%mod;
ll q = power(a,b/2);
return (q*q)%mod;
}
vector<int> adj[500005];
vector<int> leaf;
void dfs(int u,int p){
for(auto v:adj[u]){
if(v!=p){
dfs(v,u);
}
}
if(adj[u].size() == 1)
leaf.pb(u);
}
int main()
{
std::ios::sync_with_stdio(false);
int n;
cin >> n;
for(int i =2;i<=n;i++){
int u,v;
cin >> u >> v;adj[u].pb(v);adj[v].pb(u);
}
dfs(1,-1);
reverse(leaf.begin(),leaf.end());
// for(auto &x:leaf) cout << x << " ";cout<<endl;
if(leaf.size() & 1){
cout << ((leaf.size() + 1) >> 1) << endl;
for(int i = 0;i<leaf.size()-1;i+=2){
cout << leaf[i] << " " << leaf[i+1] << endl;
}
vector<bool> vis(n+1,false);
for(auto v:adj[leaf[leaf.back()]]){
vis[v] = true;
}
int node = -1,maxdeg = 0;
for(int i =1;i<=n;i++){
if(!vis[i] && adj[i].size() > maxdeg){
maxdeg = adj[i].size();
node = i;
}
}
cout << node << " " << leaf.back() << endl;
}
else{
cout << ((leaf.size() + 1) >> 1) << endl;
for(int i = 0;i<leaf.size();i+=2){
cout << leaf[i] << " " << leaf[i+1] << endl;
}
}
return 0;
}
//Hello, this is a snippet.
Compilation message
net.cpp: In function 'int main()':
net.cpp:81:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for(int i = 0;i<leaf.size()-1;i+=2){
| ~^~~~~~~~~~~~~~
net.cpp:90:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
90 | if(!vis[i] && adj[i].size() > maxdeg){
| ~~~~~~~~~~~~~~^~~~~~~~
net.cpp:99:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int i = 0;i<leaf.size();i+=2){
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
12032 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
12032 KB |
Breaking single line is causing network to disconnect. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
12032 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
12032 KB |
Breaking single line is causing network to disconnect. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
12032 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
12032 KB |
Breaking single line is causing network to disconnect. |
| 3 |
Halted |
0 ms |
0 KB |
- |
