Submission #1147146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147146		Pablo_No	늑대인간 (IOI18_werewolf)	C++20	100 / 100	619 ms	96152 KiB

werewolf

// TODO: Do sweepline.

#include "werewolf.h"

#include <bits/stdc++.h>

using namespace std;
using vi = vector<int>;

vi P;
const int BB = 22;

int find(int vv) {
    if (P[vv] == vv) return vv;
    return P[vv] = find(P[vv]);
}

vector<vi> G2;
vi ORD, ORD2, TIN, TOU, POS;
vector<vi> PR;

void dfs(int v, int p) {
    PR[v][0] = p;
    TIN[v] = ORD.size();
    ORD.push_back(v);
    for (int u : G2[v]) if (u != p) {
        dfs(u, v);
    }
    TOU[v] = ORD.size()-1;
}

void generate_intervals(int N, vector<vi> G, vi K, vi V, vi O, bool rev,
                        vi& A, vi& L, vi& R) {
    P.resize(2*N);
    for (int i = 0; i < 2*N; ++i) P[i] = i;
    G2.assign(2*N, vi(0));
    for (int i : O) {
        for (int v : G[i]) {
            if ((rev && find(v) > i) || (!rev && find(v) < i)) {
                G2[i].push_back(find(v));
                G2[find(v)].push_back(i);
                //cerr << "a" << i << ' ' << find(v) << '\n';
                P[find(v)] = i;
            }
        }
    }
    ORD.clear();
    ORD.reserve(N);
    TIN.resize(N);
    TOU.resize(N);
    PR.assign(N, vi(BB));
    dfs(O.back(), O.back());
    int Q = V.size();
    A = ORD;
    L.resize(Q);
    R.resize(Q);
    for (int xx : A) {
        //cerr << xx << ' ';
    }
    //cerr << '\n';
    ///
    for (int b = 1; b < BB; ++b) {
        for (int i = 0; i < N; ++i) {
            PR[i][b] = PR[PR[i][b-1]][b-1];
        }
    }
    for (int k = 0; k < Q; ++k) {
        int vv = K[k];
        if (!((rev && vv >= V[k]) || (!rev && vv <= V[k]))) {
            L[k] = 0;
            R[k] = -1;
            //cerr << ' ' << L[k] << ' ' << R[k] << '\n';
            continue;
        }
        for (int b = BB-1; b >= 0; --b) {
            int nv = PR[vv][b];
            if ((rev && nv >= V[k]) || (!rev && nv <= V[k])) vv = nv;
        }
        L[k] = TIN[vv];
        R[k] = TOU[vv];
        //cerr << ' ' << L[k] << ' ' << R[k] << '\n';
    }
}

vi FT;

int lsb(int x) {
    return x&(-x);
}

void ch(int p, int v) {
    ++p;
    while (p < FT.size()) {
        FT[p] += v;
        p += lsb(p);
    }
}

int rsq(int p) {
    ++p;
    int v = 0;
    while (p) {
        v += FT[p];
        p -= lsb(p);
    }
    return v;
}

int rsq(int l, int r) {
    return rsq(r)-rsq(l-1);
}

vi check_validity(int N, vi X, vi Y,
                  vi S, vi E,
                  vi L, vi R) {
    vector<vi> G(N);
    for (int i = 0; i < X.size(); ++i) {
        G[X[i]].push_back(Y[i]);
        G[Y[i]].push_back(X[i]);
    }
    vi O(N);
    for (int i = 0; i < N; ++i) O[i] = i;
    vi A, LA, RA;
    generate_intervals(N, G, E, R, O, 0, A, LA, RA);
    reverse(O.begin(), O.end());
    vi B, LB, RB;
    generate_intervals(N, G, S, L, O, 1, B, LB, RB);
    vi IB(N);
    for (int i = 0; i < N; ++i) IB[B[i]] = i;
    int Q = S.size();
    vi ANS(Q, 0);
    FT.assign(N+1, 0);
    vector<pair<int, int>> QS;
    for (int k = 0; k < Q; ++k) {
        QS.push_back({LA[k]-1, -k-1});
        QS.push_back({RA[k], +k});
    }
    //cerr << "H";
    sort(QS.begin(), QS.end());
    int cidx = -1;
    for (auto [aa, bb] : QS) {
        int cv = +1;
        if (bb < 0) {
            bb = -1-bb;
            cv = -1;
        }
        while (cidx < aa) {
            ++cidx;
            ch(IB[A[cidx]], +1);
        }
        ANS[bb] += cv*rsq(LB[bb], RB[bb]);
    }
    for (int i = 0; i < Q; ++i) {
        //cerr << ANS[i] << '\n';
        ANS[i] = min(ANS[i], 1);
    }
    return ANS;
}

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