Submission #394659

#	Time	Username	Problem	Language	Result	Execution time	Memory
394659		erfanmir	Network (BOI15_net)	C++17	100 / 100	534 ms	45444 KiB

net

// In the name of god

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 

template < class T > using ordered_set = tree < T , null_type , less < T > , rb_tree_tag , tree_order_statistics_node_update >;
  
typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define lc(x)                       (x) << 1
#define rc(x)                       (x) << 1 | 1
#define F                           first
#define S                           second
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define mp                          make_pair
ll poww(ll a, ll b, ll md) {
    ll ans = 1;
    for(; b; b >>= 1, a = a * a % md){
        if(b & 1){
            ans = ans * a % md;
        }
    }
    return ans % md;
}

const int MAXN = 5e5 + 10;
const int MAXLG = 18;
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
const ll INF = 8e18;
int n, root, ans;
vector<int> adj[MAXN], leaf;
vector<pii> res;

void dfs(int v, int p = 0){
    if((int)adj[v].size() == 1){
        leaf.push_back(v);
    }
    for(auto u : adj[v]){
        if(u == p){
            continue;
        }
        dfs(u, v);
    }
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i < n; i++){
        int v, u;
        scanf("%d %d", &v, &u);
        adj[v].push_back(u);
        adj[u].push_back(v);
    }
    for(int i = 1; i <= n; i++){
        if((int)adj[i].size() > 1){
            root = i;
            break;
        }
    }
    dfs(root);
    int sz = (int)leaf.size();
    ans = sz / 2 + (sz & 1);
    int hv = sz / 2;
    for(int i = 0; i < hv; i++){
        res.push_back(mp(leaf[i], leaf[i + hv + (sz & 1)]));
    }
    if(sz & 1){
        res.push_back(mp(leaf[hv], root));
    }

    printf("%d\n", ans);
    for(int i = 0; i < ans; i++){
        printf("%d %d\n", res[i].F, res[i].S);
    }
}

Compilation message (stderr)

net.cpp:3: warning: ignoring #pragma comment  [-Wunknown-pragmas]
    3 | #pragma comment(linker, "/stack:200000000")
      | 
net.cpp: In function 'int main()':
net.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
net.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |         scanf("%d %d", &v, &u);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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