제출 #530828

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

werewolf

#include <bits/stdc++.h>

using namespace std;
const int N = 2 * 100 * 1000 + 7;
int faul[N], faur[N], jp[21][N], p[N], k[N];
vector<int> ed[N], aed[N], q[N], ans;
set<int> sp[N];
set<int>::iterator it;

int FindL(int v)
{
    if(faul[v] == v) return v;
    faul[v] = FindL(faul[v]); return faul[v];
}

void Unionl(int a, int b)
{
    if(FindL(a) == FindL(b)) return;
    a = FindL(a); b = FindL(b);
    ed[a].push_back(b); ed[b].push_back(a);
    faul[b] = a;
}

void DFS(int v, int &pr)
{
    ++pr;
    p[v] = pr;
    //cout << v << "\n";
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        if(p[ed[v][i]] == 0)
        {
            jp[0][ed[v][i]] = v;
            DFS(ed[v][i], pr);
        }
    }
    k[v] = pr;
}

int Jump(int v, int x)
{
    for(int i = 19; i >= 0; --i)
        if(jp[i][v] >= x) v = jp[i][v];
    return v;
}

int FindR(int v)
{
    if(faur[v] == v) return v;
    faur[v] = FindR(faur[v]); return faur[v];
}

void DoJMP(int n)
{
    for(int j = 1; j <= 19; ++j)
        for(int i = 0; i < n; ++i)
            jp[j][i] = jp[j - 1][jp[j - 1][i]];
}

void UnionR(int a, int b)
{
    if(FindR(a) == FindR(b)) return;
    a = FindR(a); b = FindR(b);
    if(sp[a].size() < sp[b].size()) swap(a, b);
    faur[b] = a;
    while(sp[b].size() > 0)
    {
        sp[a].insert(*sp[b].begin()); sp[b].erase(sp[b].begin());
    }
}

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 m = X.size(), x = 0, y;
    vector<pair<int, int>> e;
    for(int i = 0; i < (int)S.size(); ++i)
    {
        q[R[i]].push_back(i);
        ans.push_back(1);
    }
    for(int i = 0; i < n; ++i) faul[i] = i;
    for(int i = 0; i < n; ++i) faur[i] = i;
    for(int i = 0; i < m; ++i)
    {
        if(X[i] > Y[i]) swap(X[i], Y[i]);
        aed[Y[i]].push_back(X[i]);
        e.push_back(make_pair(X[i], Y[i]));
    }
    sort(e.begin(), e.end());
    for(int i = m - 1; i >= 0; --i) Unionl(e[i].first, e[i].second);
    DFS(0, x);
    DoJMP(n);
    for(int i = 0; i < n; ++i) sp[i].insert(p[i]);
    for(int i = 0; i < n; ++i)
    {
        //cout << "i: " << i << " " << p[i] << "\n";
        for(int j = 0; j < (int)aed[i].size(); ++j)
            if(aed[i][j] < i)
                UnionR(i, aed[i][j]);
        for(int j = 0; j < (int)q[i].size(); ++j)
        {
            x = FindR(E[q[i][j]]);
            y = Jump(S[q[i][j]], L[q[i][j]]);
            //if(q[i][j] == 1)
                //cout << i << " " << q[i][j] << " " << x << " " << y << "\n";
            it = sp[x].lower_bound(p[y]);
            if(it == sp[x].end() || (*it) > k[y])
                ans[q[i][j]] = 0;
        }
    }
    return ans;
}

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