Submission #257728

#	Time	Username	Problem	Language	Result	Execution time	Memory
257728		VEGAnn	Village (BOI20_village)	C++14	50 / 100	91 ms	14968 KiB

Village

#include <bits/stdc++.h>
#define PB push_back
using namespace std;
const int N = 100100;
vector<int> g[N];
int n, mrk[N], ans, who_kto[N];

void dfs(int v, int p){
    for (int u : g[v]){
        if (u == p) continue;

        dfs(u, v);

        if (mrk[u] < 0){
            ans += 2;

            if (mrk[v] < 0){
                mrk[v] = u;
                mrk[u] = v;
            } else {
                mrk[u] = mrk[v];
                mrk[v] = u;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n;

    for (int i = 1; i < n; i++){
        int x, y; cin >> x >> y;
        x--; y--;

        g[x].PB(y);
        g[y].PB(x);
    }

    fill(mrk, mrk + n, -1);

    dfs(0, -1);

    if (mrk[0] < 0) {
        ans += 2;

        mrk[0] = mrk[g[0][0]];
        mrk[g[0][0]] = 0;
    }

    cout << ans << " " << ans << '\n';

    for (int i = 0; i < n; i++)
        who_kto[mrk[i]] = i;

    for (int i = 0; i < n; i++)
        cout << who_kto[i] + 1 << " ";
    cout << '\n';

    for (int i = 0; i < n; i++)
        cout << who_kto[i] + 1 << " ";
    cout << '\n';

    return 0;
}

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