제출 #1146730

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146730		kh0i	The Ties That Guide Us (CEOI23_incursion)	C++20	100 / 100	159 ms	8220 KiB

incursion

#include "bits/stdc++.h"
#include "incursion.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

using ll = long long;
using pii = pair<int, int>;

#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
    assert(l <= r);
    return uniform_int_distribution<ll> (l, r)(rng);
}

const int N = 5e4;

int n;
vector<int> g[N];
int dist[N], p[N], sz[N];

void dfs(int u, int pre = -1){
    sz[u] = 1;
    for(int v : g[u]){
        if(v == pre)
            continue;
        dist[v] = dist[u] + 1;
        p[v] = u;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

vector<int> mark(vector<pii> F, int safe){
    n = sz(F) + 1;
    for(auto [u, v] : F){
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1);
    int x = max_element(dist + 1, dist + n + 1) - dist;
    dist[x] = 0;
    dfs(x);
    int y = max_element(dist + 1, dist + n + 1) - dist;
    vector<int> diam;
    while(true){
        diam.push_back(y);
        if(y == x)
            break;
        y = p[y];
    }

    dist[safe] = 0;
    dfs(safe);

    int root = -1;
    if(sz(diam) & 1)
        root = diam[sz(diam) / 2];
    else{
        int u = diam[sz(diam) / 2];
        int v = diam[sz(diam) / 2 - 1];
        root = (dist[u] < dist[v] ? u : v);
    }

    vector<int> color(n, 0);

    while(true){
        color[root - 1] = 1;
        if(root == safe)
            break;
        root = p[root];
    }

    for(int i = 1; i <= n; ++i){
        g[i].clear();
        dist[i] = sz[i] = p[i] = 0;
    }

    return color;
}

void locate(vector<pii> F, int cur, int t){
    n = sz(F) + 1;
    debug(F);
    for(auto [u, v] : F){
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1);
    int x = max_element(dist + 1, dist + n + 1) - dist;
    dist[x] = 0;
    dfs(x);
    int y = max_element(dist + 1, dist + n + 1) - dist;
    vector<int> diam;
    while(true){
        diam.push_back(y);
        if(y == x)
            break;
        y = p[y];
    }

    int root = diam[sz(diam) / 2];

    dist[root] = 0;
    p[root] = 0;
    dfs(root);
    for(int i = 1; i <= n; ++i){
        sort(all(g[i]), [](int u, int v) -> bool{
            return sz[u] > sz[v];
        });
    }
    int pre = -1;

    debug(cur, pre);

    while(cur != root and !t){
        pre = cur;
        t = visit(p[cur]);
        cur = p[cur];
    }

    debug(cur, root);
    if(!t){
        dist[cur] = 0;
        p[cur] = 0;
        dfs(cur);
        for(int i = 1; i <= n; ++i){
            sort(all(g[i]), [](int u, int v) -> bool{
                return sz[u] > sz[v];
            });
        }
    }

    while(true){
        bool cont = 0;
        for(int v : g[cur]){
            if(v == pre or v == p[cur])
                continue;
            int nxt = visit(v);
            if(nxt){
                cur = v;
                cont = 1;
                break;
            }
            else
                visit(cur);
        }
        if(!cont)
            return;
    }
}

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