Submission #113784

#	Time	Username	Problem	Language	Result	Execution time	Memory
113784		Mercenary	Network (BOI15_net)	C++14	100 / 100	613 ms	47868 KiB

net

#include<bits/stdc++.h>

using namespace std;
#define taskname "A"
#define pb	push_back
#define mp 	make_pair
#ifndef LOCAL
#define cerr if(0)cout
#endif

typedef long double ld;
typedef long long ll;
typedef pair<int,int> ii;
const int maxn = 5e5 + 6;

int n , m;
vector<int> leaf , adj[maxn];

void dfs(int u , int v){
    if(adj[u].size() == 1){
        leaf.pb(u);
    }
    for(int c  : adj[u]){
        if(c != v)dfs(c , u);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n;
    for(int i = 1 ; i < n ; ++i){
        int u , v;cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    int root = 1;
    for(int i = 1 ; i <= n ; ++i){
        if(adj[i].size() != 1){
            dfs(i , 0);
            break;
        }else root = i;
    }
    if(leaf.size() % 2)leaf.pb(leaf.back());
    cout << leaf.size() / 2 << endl;
    for(int i = 0 ; i < leaf.size() / 2 ; i++){
        cout << leaf[i] << " " << leaf[i + leaf.size() / 2] << '\n';
    }
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:51:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < leaf.size() / 2 ; i++){
                     ~~^~~~~~~~~~~~~~~~~
net.cpp:42:9: warning: variable 'root' set but not used [-Wunused-but-set-variable]
     int root = 1;
         ^~~~
net.cpp:33:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
net.cpp:34:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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