Submission #857956

#	Time	Username	Problem	Language	Result	Execution time	Memory
857956		Trisanu_Das	Village (BOI20_village)	C++17	50 / 100	76 ms	18256 KiB

Village

#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
ll n, ans[100005], resx;
vector<ll> adj[100005];
 
pair<ll, ll> S(ll x, ll y){
    vector<pair<ll, ll> > a;
    a.clear();
    pair<ll, ll> b;
    for(int i = 0; i < adj[x].size(); i++){
        if(adj[x][i] != y){
            b = S(adj[x][i], x);
            if(b.first == b.second) a.push_back(b);
        }
    }
    if(a.size() == 0){
        if(y == 0){
            ans[b.second] = x;
            ans[x] = b.first;
            resx += 2;
            return {0, 0};
        }else return {x, x};
    }else{
        a.push_back({x, x});
        ll m = a.size() - 2;
        for(int i=0;i<=m;i++){
            ans[a[i].first] = a[i + 1].first;
            resx += 2;
        }
        ans[x] = a[0].first;
        return {x, a[m].first};
    }
}
 
int main(){
    cin >> n;
    for(int i=1;i<n;i++){
        ll u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    S(1, 0);
    cout << resx << ' ' << 0 << '\n';
    for(int i = 1; i <= n; i++) cout << ans[i] << ' ';
    cout << '\n';
    for(int i = 1; i <= n; i++) cout << i << ' ';
    cout << '\n';
}

Compilation message (stderr)

Village.cpp: In function 'std::pair<long long int, long long int> S(long long int, long long int)':
Village.cpp:12:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i = 0; i < adj[x].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~

• Subtask 1: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50