Submission #650557

#	Time	Username	Problem	Language	Result	Execution time	Memory
650557		DJeniUp	Village (BOI20_village)	C++17	50 / 100	138 ms	19368 KiB

Village

#include "bits/stdc++.h"
//#pragma GCC optimize("O3")
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef long double ld;
 
#define fr first
#define sc second
#define pb push_back
#define INF 100000000007
#define endl '\n'
#define MOD 998244353
#define A 31
#define N 100007
#define eps 0.000000000001
 
ll n,res[N],resx;

vector<ll>v[N];

pairll S(ll x,ll y){
    vector<pairll>a;
    a.clear();
    pairll b;
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]!=y){
            b=S(v[x][i],x);
            if(b.fr==b.sc)a.pb(b);
        }
    }
    if(a.size()==0){
        if(y==0){
            res[b.sc]=x;
            res[x]=b.fr;
            resx+=2;
            return {0,0};
        }else return {x,x};
    }else{
        a.pb({x,x});
        ll m=a.size()-2;
        for(int i=0;i<=m;i++){
            res[a[i].fr]=a[i+1].fr;
            resx+=2;
        }
        res[x]=a[0].fr;
        return {x,a[m].fr};
    }
}

int main(){
    
    cin>>n;
    for(int i=1;i<n;i++){
        ll x,y;
        cin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    S(1,0);
    cout<<resx<<" "<<0<<endl;
    for(int i=1;i<=n;i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;
    for(int i=1;i<=n;i++){
        cout<<i<<" ";
    }
    cout<<endl;
    
    
    return 0;
}

Compilation message (stderr)

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

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