Submission #1224612

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

incursion

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

int visit(int 𝑣);

vector<int> mark(vector<pair<int, int>> F, int safe) {
    int N = F.size()+2;
    vector<vector<int>> adj(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;
    function<void(int, int)> dfs = [&](int a, int p) -> void {
        for (int x : adj[a]) {
            if (x == p) continue;
            ret[x] = (ret[a]+2)%3;
            dfs(x, a);
        }
    };
    dfs(safe, 0);
    ret.erase(ret.begin());
    return ret;
}

void locate(vector<pair<int, int>> F, int curr, int t) {
    int N = F.size()+2; 
    vector<vector<int>> adj(N);
    for (auto x : F) {
        adj[x.first].push_back(x.second);
        adj[x.second].push_back(x.first);
    }
    vector<int> depth(N, 0);
    /*
    vector<int> seen(N, -1);
    seen[curr] = t;
    auto visitme = [&](int a) -> int {
        if (seen[a] == -1) seen[a] = visit(a);
        return seen[a];
    };*/

    function<void(int, int)> dfs = [&](int a, int p) {
        for (int x : adj[a]) {
            if (x == p) continue;
            dfs(x, a);
            depth[a] = max(depth[x]+1, depth[a]);
        }
    };
    dfs(curr, 0);

    int prev = 0;
    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;
            }
        }
    }
    cout << "nogood";
    return;
}

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