Submission #1065258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065258		Malix	Network (BOI15_net)	C++14	100 / 100	388 ms	54004 KiB

net

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

vii a;
vi p,arr;

void dfs(int x){
    if(a[x].size()==1)arr.PB(x+1);
    for(auto u:a[x]){
        if(p[x]==u)continue;
        p[u]=x;
        dfs(u);
    }
}

int main() {   
    int n;cin>>n;
    a.resize(n);p.resize(n,-1);
    REP(i,0,n-1){
        int x,y;cin>>x>>y;
        x--;y--;
        a[x].PB(y);a[y].PB(x);
    }
    dfs(0);
    cout<<(arr.size()+1)/2<<"\n";
    if(arr.size()%2)cout<<arr.front()<<" "<<arr.back()<<"\n";
    REP(i,0,arr.size()/2)cout<<arr[i]<<" "<<arr[arr.size()/2+i]<<"\n";
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:13:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define REP(i,a,b) for(int i=a;i<b;i++)
......
   47 |     REP(i,0,arr.size()/2)cout<<arr[i]<<" "<<arr[arr.size()/2+i]<<"\n";
      |         ~~~~~~~~~~~~~~~~         
net.cpp:47:5: note: in expansion of macro 'REP'
   47 |     REP(i,0,arr.size()/2)cout<<arr[i]<<" "<<arr[arr.size()/2+i]<<"\n";
      |     ^~~

• Subtask 1: 18 / 18
• Subtask 2: 45 / 45
• Subtask 3: 37 / 37