Submission #1168582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168582		anmattroi	The Ties That Guide Us (CEOI23_incursion)	C++17	0 / 100	141 ms	17180 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];

vector<int> adj[maxn];

void pfs(int u, int dad) {
    par[u] = dad;
    sz[u] = 1;
    for (int v : adj[u])
        if (v != dad) {
            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);
    if (n % 2 == 0) {
        int centroid2 = 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];
        if (centroid2) {
            if (safe == centroid1 || safe == centroid2) {
                vector<int> ans(n, 0);
                ans[safe-1] = 1;
                return ans;
            }
        }
    }
    root = find_centroid(1, 0);
    pfs(root, 0);
    vector<int> ans(n, 0);
    while (safe) {
        ans[safe-1] = 1;
        safe = par[safe];
    }
    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;
    }
    if (root == curr) {
        for (int v : adj[curr]) {
            if (cached.count(v)) continue;
            int orz = visit(v);
            cached[v] = orz;
            if (!orz) {
                visit(root);
                continue;
            }
            curr = v;
            t = orz;
            break;
        }
        if (curr == root) return;
    } else 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);
        int last = curr;
        for (int v : adj[curr])
            if (!cached.count(v)) {
                int orz = visit(v);
                if (!orz) {
                    visit(curr);
                    return;
                }
                curr = orz;
                cached[curr] = orz;
                break;
            }
        if (curr == last) return;
    }

}

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