Submission #1224581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224581		LaMatematica14	The Ties That Guide Us (CEOI23_incursion)	C++20	12 / 100	146 ms	7248 KiB

incursion

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;

int visit(int 𝑣);

void dfs(int a, int p, vector<int> &ret) {
    for (int x : adj[a]) {
        if (x == p) continue;
        ret[x] = (ret[a]+2)%3;
        dfs(x, a, ret);
    }
}

void dd(int a, int p, vector<int> &d) {
    d[a] = 0;
    for (int x : adj[a]) {
        if (x == p) continue;
        dd(x, a, d);
        d[a] = max(d[x]+1, d[a]);
    }
}

vector<int> mark(vector<pair<int, int>> F, int safe) {
    int N = F.size()+2;
    adj.resize(N);
    for (auto x : F) {
        adj[x.first].push_back(x.second);
        adj[x.second].push_back(x.first);
    }
    vector<int> ret(N);
    ret[safe] = 2;
    dfs(safe, -1, ret);
    ret.erase(ret.begin());
    return ret;
}

void locate(vector<pair<int, int>> F, int curr, int t) {
    int N = F.size()+2;
    adj.clear();
    adj.resize(N);
    for (auto x : F) {
        adj[x.first].push_back(x.second);
        adj[x.second].push_back(x.first);
    }
    vector<int> depth(N);
    vector<int> seen(N, -1);
    seen[curr] = t;
    auto visitme = [&](int a) -> int {
        if (seen[a] == -1) seen[a] = visit(a);
        return seen[a];
    };
    dd(curr, -1, depth);
    int prev = -1;
    while (1) {
        int best = adj[curr][0], other = -1;
        if (best == prev) {
            if (adj[curr].size() == 1) return; // ok?
            best = adj[curr][1];
        }
        for (int x : adj[curr]) {
            if (x == prev || x == best) continue;
            if (depth[best] < depth[x]) {
                other = best;
                best = x;
            } else other = x;
        }
        
        prev = curr;
        int aus = visit(best);
        if (aus == (t+1)%3) curr = best, t = aus;
        else {
            visit(curr);
            if (other == -1) return;
            aus = visit(other);
            if (aus == (t+1)%3) curr = other, t = aus;
            else {
                visit(curr);
                return;
            }
        }
    }
    return;
}

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