Submission #1168625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168625		anmattroi	The Ties That Guide Us (CEOI23_incursion)	C++17	100 / 100	185 ms	18120 KiB

incursion

#include "incursion.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define maxn 450005
using namespace std;

int n, root, sz[maxn], par[maxn], depth[maxn];

vector<int> adj[maxn];

void pfs(int u, int dad) {
    par[u] = dad;
    sz[u] = 1;
    for (int v : adj[u])
        if (v != dad) {
            depth[v] = depth[u]+1;
            pfs(v, u);
            sz[u] += sz[v];
        }
}

int find_centroid(int u, int dad) {
    for (int v : adj[u])
        if (v != dad && sz[v] > n/2) return find_centroid(v, u);
    return u;
}

vector<int> mark(vector<pair<int, int>> F, int safe) {
    n = F.size()+1;
    for (auto [u, v] : F) {
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    pfs(1, 0);
    int centroid1 = find_centroid(1, 0), centroid2 = -1;
    if (n % 2 == 0) {
        for (int v : adj[centroid1])
            if (v != par[centroid1] && sz[v] == n/2) {
                centroid2 = v;
                break;
            }
        if (sz[centroid1] == n/2) centroid2 = par[centroid1];
    }
    pfs(safe, 0);

    if (centroid2 != -1 && depth[centroid1] > depth[centroid2]) swap(centroid1, centroid2);
    vector<int> ans(n, 0);
    while (centroid1) {
        ans[centroid1-1] = 1;
        centroid1 = par[centroid1];
    }
    return ans;
}


map<int, int> cached;

void locate(vector<pair<int, int>> F, int curr, int t) {
    n = F.size()+1; cached.clear();
    for (int i = 1; i <= n; i++) adj[i].clear();
    for (auto [u, v] : F) {
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    pfs(1, 0);
    root = find_centroid(1, 0);
    pfs(root, 0);
    cached[curr] = t;
    while (t == 0 && curr != root) {
        t = visit(curr = par[curr]);
        cached[curr] = t;
    }
    cached[par[curr]] = -1;
    while (1) {
        int mxsz = -1, bigChild = -1;
        for (int v : adj[curr])
            if (!cached.count(v)) {
                if (mxsz < sz[v]) {
                    mxsz = sz[v];
                    bigChild = v;
                }
        }
        if (mxsz == -1) return;
        int T = visit(bigChild);
        cached[bigChild] = T;
        if (T) {
            curr = bigChild;
            continue;
        }
        visit(curr);
    }

}

• Subtask 0: 0 / 0
• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40