제출 #659643

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
659643		someone	늑대인간 (IOI18_werewolf)	C++14	0 / 100	272 ms	31524 KiB

werewolf

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

const int N = 2e5 + 42;

vector<int> adj[N], req[N];
int n, m, q, sz[N], par[N], pds[N];

int F1(int i) {
    if(sz[i] < 0)
        return i;
    return F1(sz[i]);
}

int F2(int i) {
    if(par[i] == i)
        return i;
    return par[i] = F2(par[i]);
}

void U1(int a, int b) {
    int x = min(a, b);
    a = F1(a), b = F1(b);
    if(a == b)
        return;
    if(-sz[a] < -sz[b])
        swap(a, b);
    sz[a] += sz[b];
    sz[b] = a;
    pds[b] = x;
}

void U2(int a, int b) {
    a = F2(a), b = F2(b);
    if(a < b)
        swap(a, b);
    par[b] = a;
}

int possible(int a, int b, int auth) {
    while(sz[a] >= 0 && pds[a] >= auth)
        a = sz[a];
    while(sz[b] >= 0 && pds[b] >= auth)
        b = sz[b];
    return a == b;
}

vector<int> check_validity(int NB, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    n = NB, m = X.size(), q = S.size();
    vector<int> ans(q);
    for(int i = 0; i < n; i++)
        par[i] = i, sz[i] = -1;
    for(int i = 0; i < m; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    
    for(int i = n-1; i >= 0; i--)
        for(int j : adj[i])
            if(j > i)
                U1(i, j);
    
    for(int i = 0; i < q; i++)
        req[R[i]].push_back(i);
    
    for(int i = 0; i < n; i++) {
        for(int j : adj[i])
            if(j < i)
                U2(i, j);
        for(int j : req[i])
            ans[j] = possible(F2(E[j]), S[j], L[j]);
    }
    return ans;
}

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