Submission #1160050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160050		countless	Village (BOI20_village)	C++20	0 / 100	0 ms	328 KiB

Village

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef set<int> si;
typedef set<long long> sll;

const ll MOD = 998244353;
const ld EPS = 1e-12;

#define endl "\n"
#define sp <<" "<<
#define forn(i, n) for(ll i = 0; i < n; i++)
#define rforn(i, n) for(ll i = n; i >= 0; i--)
#define dbg(x) cout << #x << " = " << x << endl
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define INF 1e18
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())

int N;
int mn = 0, mx = 0;
vector<int> ansMin, ansMax;
vector<int> depth;

int treeCenter(vector<vector<int>> &adj) {
    vector<int> deg(N, 0);
    vector<int> leaves;

    for (int i = 0; i < N; i++) {
        deg[i] = adj[i].size();
        if (deg[i] == 0 || deg[i] == 1) {
            leaves.push_back(i);
            deg[i] = 0;
        }
    }

    int count = leaves.size();
    while (count < N) {
        vector<int> newLeaves;
        for (auto node : leaves) {
            for (auto neighbor : adj[node]) {
                deg[neighbor]--;
                if (deg[neighbor] == 1) {
                    newLeaves.push_back(neighbor);
                }
            }

            deg[node] = 0;
        }

        count += newLeaves.size();
        leaves = newLeaves;
    }

    return leaves[0];
}

void findDepth(int node, int parent, int dep, vector<vector<int>> &adj, vector<int> &depth) {
    depth[node] = dep;
    for (auto neighbor : adj[node]) {
        if (neighbor == parent) continue;
        findDepth(neighbor, node, dep + 1, adj, depth);
    }
}

void minCase(int node, vector<vector<int>> &adj, vector<bool> &vis) {
    int parent = -1;
    for (auto neighbor : adj[node]) {
        if (depth[neighbor] < depth[node]) {
            parent = neighbor;
            break;
        }
    }

    // we are at an isolated root
    if (parent == -1) {
        vis[node] = true;
        mn += 2;
        swap(ansMin[node], ansMin[adj[node][0]]);
    }

    else {
        if (vis[parent]) return; // don't know why this call is needed but it works...
        vis[parent] = true;
        for (auto neighbor : adj[parent]) {
            if (depth[neighbor] < depth[parent]) continue;
            if (vis[neighbor]) continue;
            
            vis[node] = true;
            mn += 2;
            swap(ansMin[parent], ansMin[neighbor]);
        }
    }

    return;
}

void solution() {
    cin >> N;
    ansMin.resize(N);
    ansMax.resize(N);

    for (int i = 0; i < N; i++) {
        ansMin[i] = i;
        ansMax[i] = i;
    }

    vector<vector<int>> adj(N);

    for (int i = 0; i < N - 1; i++) {
        int u, v; cin >> u >> v;
        u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int center = treeCenter(adj);
    depth.resize(N);
    findDepth(center, -1, 0, adj, depth);

    // min case
    vector<bool> vis(N, false);
    vector<pair<int, int>> depthCopy(N);
    for (int i = 0; i < N; i++) {
        depthCopy[i] = {depth[i], i};
    }
    sort(rall(depthCopy));

    for (int i = 0; i < N; i++) {
        if (!vis[depthCopy[i].second]) {
            minCase(depthCopy[i].second, adj, vis);
        }
    }

    


    // print the answer
    cout << mn sp mx << endl;
    for (int x : ansMin) cout << x + 1 << " ";
    cout << endl;
    for (int x : ansMax) cout << x + 1 << " ";
    cout << endl;

    return;
}

signed main() {
    fast_io();

    solution();

    // int tests; cin >> tests;
    // while (tests--) {
    //     solution();
    // }

    return 0;
}

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