Submission #255083

#	Time	Username	Problem	Language	Result	Execution time	Memory
255083		davitmarg	Village (BOI20_village)	C++17	100 / 100	96 ms	16756 KiB

Village

/*
DavitMarg
In a honky-tonk,
Down in Mexico
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0)
using namespace std;

const int N = 200005;

int n, used[N], vin[N], ans1[N],ans2[N], sz[N], sum1,cnt[N];
LL sum2;
vector<int> g[N],d;

void dfs(int v, int p)
{
    vin[v] = v;
    sz[v] = g[v].size();
    cnt[v] = 1;
    for (int i = 0; i < g[v].size(); i++)
    {
        int to = g[v][i];
        if (to == p)
            continue;
        dfs(to, v);
        sz[v]--;
        cnt[v] += cnt[to];
    }
    d.PB(v);
    sum2 += min(cnt[v], n - cnt[v]);
    if (!used[v] || (v != p && sz[p] == 1 && !used[p]))
    {
        swap(vin[v], vin[p]);
        ans1[vin[p]] = p;
        ans1[vin[v]] = v;
        used[v] = used[p] = 1;
        sum1 += 2;
    }
}

int main()
{
    fastIO;
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1, 1);
    for (int i = 0; i < n; i++)
        ans2[d[i]] = d[(i + n / 2) % n];
    cout << sum1 << " " << sum2+sum2 << endl;
    for (int i = 1; i <= n; i++)
        cout << ans1[i] << " ";
    cout << endl;
    for (int i = 1; i <= n; i++)
        cout << ans2[i] << " ";
    cout << endl;

    return 0;
}

/*


*/

Compilation message (stderr)

Village.cpp: In function 'void dfs(int, int)':
Village.cpp:43:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++)
                     ~~^~~~~~~~~~~~~

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