제출 #773427

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
773427		IBory	늑대인간 (IOI18_werewolf)	C++17	0 / 100	4049 ms	92784 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 200007;
int _P[MAX], P[18][MAX], D[MAX];
pii UD[18][MAX];
vector<int> TG[MAX], G[MAX];

int Find(int n) {
    if (n == _P[n]) return n;
    return _P[n] = Find(_P[n]);
}

int Union(int a, int b) {
    a = Find(a), b = Find(b);
    if (a == b) return 0;
    _P[a] = b;
    return 1;
}

void DFS(int cur, int prev) {
    D[cur] = D[prev] + 1;
    P[0][cur] = prev;
    UD[0][cur] = {cur, cur};
    for (int next : G[cur]) {
        if (next == prev) continue;
        DFS(next, cur);
    }
}

int LCA(int a, int b) {
    if (D[a] > D[b]) swap(a, b);
    for (int i = 17; i >= 0; --i) if ((D[b] - D[a]) & (1 << i)) b = P[i][b];
    if (a == b) return a;
    for (int i = 17; i >= 0; --i) {
        if (P[i][a] == P[i][b]) continue;
        a = P[i][a], b = P[i][b];
    }
    return P[0][a];
}

pii PathQuery(int a, int b) {
    int c = LCA(a, b);
    //cout << a << ' ' << b << ' ' << c << '\n';
    pii ret = {1e9, 0};
    for (int i = 17; i >= 0; --i) {
        if ((1 << i) & (D[a] + 1 - D[c])) {
            ret.first = min(ret.first, UD[i][a].first);
            ret.second = max(ret.second, UD[i][a].second);
            //cout << "Up " << i << ' ' << a << '\n';
            a = P[i][a];
        }
        if ((1 << i) & (D[b] + 1 - D[c])) {
            ret.first = min(ret.first, UD[i][b].first);
            ret.second = max(ret.second, UD[i][b].second);
            //cout << "Up " << i << ' ' << b << '\n';
            b = P[i][b];
        }
    }
    return ret;
}

int KP(int a, int k) {
    for (int i = 17; i >= 0; --i) if (k & (1 << i)) a = P[i][a];
    return a;
}

int ToC(int a, int b, int c, int d) {
    int cut = D[a] - D[c] + 1, dist = D[a] + D[b] - 2 * D[c] + 1;
    if (d <= cut) return KP(a, d - 1);
    return KP(b, dist - d);
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    int Q = S.size(), M = X.size();
    for (int i = 0; i < M; ++i) {
        TG[X[i]].push_back(Y[i]);
        TG[Y[i]].push_back(X[i]);
    }
    for (int i = 0; i < N; ++i) sort(TG[i].begin(), TG[i].end(), greater<int>());
    
    iota(_P, _P + N, 0);
    for (int i = 0; i < N; ++i) {
        for (int j : TG[i]) {
            if (i < j || !Union(i, j)) continue;
            //cout << "EDGE " << i << ' ' << j << '\n';
            G[i].push_back(j);
            G[j].push_back(i);
        }
    }

    DFS(0, 0);
    for (int i = 1; i < 18; ++i) for (int n = 0; n < N; ++n) {
        P[i][n] = P[i - 1][P[i - 1][n]];
        UD[i][n] = {min(UD[i - 1][n].first, UD[i - 1][P[i - 1][n]].first), max(UD[i - 1][n].second, UD[i - 1][P[i - 1][n]].second)};
        //cout << i << ' ' << n << ' ' << UD[i][n].first << ' ' << UD[i][n].second << '\n';
    }
    
    vector<int> ans;
    for (int i = 0; i < Q; ++i) {
        int a = S[i], b = E[i], c = LCA(a, b);
        int noA = L[i] - 1, noB = R[i] + 1;

        pii pathInfo = PathQuery(a, b);
        if (noA < pathInfo.first || pathInfo.second < noB) {
            //cout << a << ' ' << b << " / " << pathInfo.first << ' ' << pathInfo.second << " SKIP\n";
            ans.push_back(1);
            continue;
        }

        int dist = D[a] + D[b] - 2 * D[c] + 1;
        int qL = -1, qR = dist;
        int bL = 0, bR = dist + 1;
        while (bL + 1 < bR) {
            int mid = (bL + bR) / 2;
            pii t = PathQuery(a, ToC(a, b, c, mid));
            (t.first <= noA ? bR : bL) = mid;
        }
        qR = bR;

        bL = 0, bR = dist + 1;
        while (bL + 1 < bR) {
            int mid = (bL + bR) / 2;
            pii t = PathQuery(b, ToC(b, a, c, mid));
            (t.second >= noB ? bR : bL) = mid;
        }
        qL = dist + 1 - bR;

        //cout << qL << ' ' << qR << '\n';
        ans.push_back(qL + 1 < qR);
    }

    return ans;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51