제출 #418897

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
418897		Berted	늑대인간 (IOI18_werewolf)	C++14	100 / 100	1066 ms	90048 KiB

werewolf

#include "werewolf.h"
#include <vector>
#include <set>
#include <algorithm>

#include <iostream>

#define vi vector<int>
#define pii pair<int, int>
#define ppp pair<pii, pii>
#define ppt pair<ppp, int>
#define fst first
#define snd second

using namespace std;

const int LG = 18;

int N, M, Q, par[200001], lf[200001], rg[200001], t = 0;
ppt A[200001];
vi adj[200001], tr[200001]; 

set<int> dt[200001];

int sps[200001][LG];

int find(int x) {return par[x] = (par[x] == x) ? x : find(par[x]);}
inline void join(int a, int b, int t)
{
    //cerr << "J: " << a << " " << b << "\n";
    a = find(a), b = find(b);
    if (a != b)
    {
        if (t) 
        {  
            if (dt[a].size() < dt[b].size()) swap(a, b);
            par[b] = a;
            while (dt[b].size())
            {
                dt[a].insert(*dt[b].begin());
                dt[b].erase(dt[b].begin());
            }
        } 
        else 
        {
            par[b] = a;
            //cerr << a << " -> " << b << "\n";
            tr[a].push_back(b);
        }
    }
}

void DFS(int u, int p)
{
    sps[u][0] = p;
    //cerr << u << " " << p << "\n";
    for (int i = 1; i < LG; i++)
    {
        if (sps[u][i - 1] == -1) sps[u][i] = -1;
        else sps[u][i] = sps[sps[u][i - 1]][i - 1];
    }
    lf[u] = t++;
    for (const auto &v : tr[u]) DFS(v, u);
    rg[u] = t - 1;
}

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) 
{
    ::N = N; M = X.size(); Q = S.size();
    vi ret(Q, 0);

    for (int i = 0; i < N; i++) par[i] = i;
    for (int i = 0; i < M; i++)
    {
        if (X[i] > Y[i]) swap(X[i], Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    for (int u = 1; u < N; u++)
    {
        for (const auto &v : adj[u]) join(u, v, 0);
    }

    for (int u = 0; u < N; u++)
    {
        if (par[u] == u) DFS(u, -1);
        adj[u].clear();
    }
    for (int i = 0; i < M; i++) {adj[X[i]].push_back(Y[i]);}

    for (int i = 0; i < Q; i++)
    {
        A[i].fst.fst = {L[i], R[i]}; A[i].fst.snd = {S[i], E[i]};
        A[i].snd = i;
    }

    sort(A, A + Q);
    int j = Q - 1;
    for (int i = N - 1; i >= 0; i--)
    {
        dt[i].insert(lf[i]); par[i] = i;
        for (const auto &v : adj[i]) 
        {
            //cerr << "J1: " << i << " " << v << "\n";
            join(i, v, 1);
        }
        for (; j >= 0 && A[j].fst.fst.fst >= i; j--)
        {
            int r = A[j].fst.fst.snd, s = A[j].fst.snd.fst, e = A[j].fst.snd.snd, id = A[j].snd;
            for (int k = LG - 1; k >= 0; k--)
            {
                if (sps[e][k] == -1) continue;
                else if (sps[e][k] <= r) {e = sps[e][k];}
            }

            s = find(s);
            auto it = dt[s].lower_bound(lf[e]);
            ret[id] = (it != dt[s].end() && *it <= rg[e]);
        }
    }
    
    return ret;
}

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