Submission #655926

#	Time	Username	Problem	Language	Result	Execution time	Memory
655926		nolimiya	Network (BOI15_net)	C++14	100 / 100	575 ms	84352 KiB

net

#include <bits/stdc++.h>
#include <math.h>
//in the name of god,aka allah
//**gray sety orz**
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define pi pair<long long , long long>
#define pii pair<long long , pair<long long , long long>>
const int maxm = 5e5 +4;
const long long mod = 1e9 + 7 ;
typedef long long ll;
ll l,r,mid;
ll n,m;
ll dis[maxm] , sum[maxm];
bool isval(int mid){
    //cout << mid <<" " << mid*mid-mid <<endl;
    if (((mid-1)*mid)/2 < m) return 0;
    return 1;
}
int darage[maxm] , ss , mm;
queue<int> q;
vector<int> g[maxm] , z[maxm];
ll sath[maxm];
bool vis[maxm] , gos[maxm];
int pedaret[maxm];
ll get_par(ll v){
    if (pedaret[v]==v) return v;
    return pedaret[v] = get_par(pedaret[v]);
}
ll pars1[maxm] , pars2[maxm];
vector<ll> se[maxm];
map<int,int> st[maxm];
int rp[maxm];
pi w[maxm];
ll dp[maxm];
//ll rw[maxm][maxm];
map<ll,ll> mp;
vector<int> vec;
void dfs(int k,int jad = 1){
    for (auto x : g[k]){
        if (jad!=x) dfs(x,k);
    }
    if (g[k].size()==1) vec.push_back(k);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >>n;
    for (int i=1; i<n; i++){
        cin >>l>>r;
        g[l].push_back(r),g[r].push_back(l); 
    }
    dfs(1);
    cout<<(vec.size()+1)/2<<endl;
    if (vec.size()%2==0){
        for (int i=0; i<vec.size()/2; i++) cout<<vec[i]<<" "<<vec[i+vec.size()/2]<<endl;
    }
    else{
        for (int i=0; i<vec.size()/2; i++) cout<<vec[i]<<" "<<vec[i+vec.size()/2+1]<<endl;
        cout<<vec[0]<<" "<<vec[vec.size()/2];
    }
}

Compilation message (stderr)

net.cpp:5: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    5 | #pragma comment(linker, "/stack:200000000")
      | 
net.cpp: In function 'int main()':
net.cpp:57:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int i=0; i<vec.size()/2; i++) cout<<vec[i]<<" "<<vec[i+vec.size()/2]<<endl;
      |                       ~^~~~~~~~~~~~~
net.cpp:60:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for (int i=0; i<vec.size()/2; i++) cout<<vec[i]<<" "<<vec[i+vec.size()/2+1]<<endl;
      |                       ~^~~~~~~~~~~~~

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