Submission #122204

#	Time	Username	Problem	Language	Result	Execution time	Memory
122204		Gustav	Network (BOI15_net)	C++14	100 / 100	605 ms	45340 KiB

net

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pi> vpi;
typedef vector<vi> vvi;
const int inf = 0x3f3f3f3f;
const ll linf = 123456789012345678;
const ll mod = 998244353;
#pragma GCC optimize("Ofast")
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl

int n;
vvi conn;
vpi ans;

pi dfs(int node, int par){
    if(conn[node].size() == 1) return {node, -1};
    pi m = {-1, -1};
    for(auto x : conn[node]){
        if(x == par) continue;
        pi r = dfs(x, node);
        if(m.first == -1) m = r;
        else{
            if(m.second != -1 || r.second != -1){
                ans.push_back({m.first, r.first});
                if(m.second == -1) m = {r.second, m.second};
                else m = {m.second, r.second};
            }
            else{
                m.second = r.first;
            }
        }
    }
    return m;
}

int main(){
    cin.sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    conn = vvi(n);
    for(int i = 0; i < n-1; i++){
        int u, v;
        cin >> u >> v;
        u--, v--;
        conn[u].push_back(v);
        conn[v].push_back(u);
    }

    int root = 0;
    while(conn[root].size() == 1) root++;

    pi r = dfs(root, -1);
    if(r.second != -1){
        ans.push_back({r.first, r.second});
    }
    else{
        ans.push_back({root, r.first});
    }

    cout << ans.size() << "\n";
    for(int i = 0; i < ans.size(); i++) cout << ans[i].first+1 << " " << ans[i].second+1 << "\n";
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:68:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ans.size(); i++) cout << ans[i].first+1 << " " << ans[i].second+1 << "\n";
                    ~~^~~~~~~~~~~~

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