Submission #915286

#	Time	Username	Problem	Language	Result	Execution time	Memory
915286		Amr	Village (BOI20_village)	C++14	0 / 100	3 ms	7516 KiB

Village

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define S second
#define F first
#define all(x) (x).begin(),(x).end()
#define sz size()
#define Yes cout << "YES" << endl
#define No cout << "NO" << endl
#define pb(x) push_back(x);
#define endl '\n'
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int N=3e5+7;
ll INF=INT_MAX,mod=1e9+7;
int TT=1;
ll power(ll x, unsigned int y)
{
    ll res = 1;
    x = x; // % mod;
    if (x == 0) return 0;
    while (y > 0)
    {
        if (y & 1) res = (res*x)  ; // % mod;
        y = y>>1;
        x = (x*x) ; // % mod;
    }
    return res;
}
ll ans = 0;
vector<ll> v[N];
ll mxdep = 0;

void dfs(ll x, ll par, ll dep)
{
    mxdep = max(dep,mxdep);
    if(dep&1) ans++;
    for(int i = 0; i < v[x].sz; i++)
    {
        ll newn = v[x][i];
        if(newn==par) continue;
        dfs(newn,x,dep+1);

    }
}
ll best[N];
void dfs2(ll x, ll par, ll dep)
{

    if(dep&1)
    {
        ll lst = x;
        if(v[x].back()==par) best[x] = v[x][v[x].sz-2];
        else best[x] = v[x].back();
        for(int newn : v[x])
        {
            if(newn==par) continue;
            best[newn] = lst;
            lst = newn;
        }
    }
    for(int newn: v[x])
    {
        if(newn==par) continue;
        dfs2(newn,x,dep+1);
    }
}
void solve()
{
    ll n; cin >> n;
    for(int i = 0; i < n-1; i++)
    {
        ll x, y; cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    ll mn = 1e18, cnt;
    for(int i = 1; i <= n ;i++)
    {
        ans = 0;
        mxdep = 0;
    dfs(i,0,1);
    if(mxdep%2==1) continue;
   // cout << i << " " << ans << " ";
    ans = (2*ans) + (n-2*ans)*2;
    //cout << ans << endl;
    if(ans<mn) { cnt = i , mn= ans;}
    }
    dfs2(cnt,0,1);
    cout << mn << " " << 1 << endl;
    for(int i = 1; i <= n; i++)
    {
        cout << best[i] << " ";
    }
    cout << endl;

    for(int i = 1; i <= n; i++) cout << 1 << " ";
    cout << endl;
}
int main(){
    //freopen("friday.in","r",stdin);
    //freopen("friday.out","w",stdout);
    fast;
    //cin >> TT;
    while(TT--)
        solve();

    return 0;
}

Compilation message (stderr)

Village.cpp: In function 'void dfs(ll, ll, ll)':
Village.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i = 0; i < v[x].sz; i++)
      |                      ^
Village.cpp: In function 'void solve()':
Village.cpp:89:9: warning: 'cnt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   89 |     dfs2(cnt,0,1);
      |     ~~~~^~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 38
• Subtask 3: 0 / 50