Submission #1191519

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191519		alexdd	Werewolf (IOI18_werewolf)	C++20	15 / 100	4094 ms	72804 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> con[200005],con_arb[200005];
int tin[200005][2],tout[200005][2],timer,who[200005][2];
int anc[200005][18][2];

int parent[200005][2];

int father[200005],siz[200005],sus[200005];
void init()
{
    for(int i=0;i<n;i++)
        father[i]=i, siz[i]=1, sus[i]=i;
}
int gas(int x)
{
    if(father[x]!=x)
        father[x] = gas(father[x]);
    return father[x];
}
void unite(int x, int y, int c)//x are prioritate
{
    x = gas(x);
    y = gas(y);
    if(x==y)
        return;
    if(siz[x] >= siz[y])
    {
        father[y] = x;
        parent[sus[y]][c] = sus[x];
        siz[x] += siz[y];
    }
    else
    {
        parent[sus[y]][c] = sus[x];
        sus[y] = sus[x];
        father[x] = y;
        siz[y] += siz[x];
    }
}

void dfs(int nod, int c)
{
    timer++;
    who[timer][c] = nod;
    tin[nod][c] = timer;
    for(int adj:con_arb[nod])
    {
        dfs(adj,c);
    }
    tout[nod][c] = timer;
}

void calc_arb(int c)
{
    for(int i=0;i<n;i++)
    {
        parent[i][c] = -1;
        con_arb[i].clear();
    }
    vector<int> ord;
    if(c==0)
    {
        for(int i=0;i<n;i++)
            ord.push_back(i);
    }
    else
    {
        for(int i=n-1;i>=0;i--)
            ord.push_back(i);
    }
    init();
    vector<bool> apare(n,0);
    for(int i:ord)
    {
        apare[i] = 1;
        for(int x:con[i])
        {
            if(apare[x])
            {
                unite(i,x,c);
            }
        }
    }
    //for(int i=0;i<n;i++) cerr<<i<<" "<<parent[i][c]<<"   "<<c<<" parent\n";
    for(int i=0;i<n;i++)
    {
        if(parent[i][c]==-1)
        {
            anc[i][0][c] = i;
        }
        else
        {
            anc[i][0][c] = parent[i][c];
            con_arb[parent[i][c]].push_back(i);
        }

    }
    for(int p=1;p<18;p++)
        for(int i=0;i<n;i++)
            anc[i][p][c] = anc[anc[i][p-1][c]][p-1][c];
    timer=0;
    dfs(ord.back(),c);
}
int get_anc(int nod, int c, int lim)
{
    if(c==1)
    {
        for(int p=17;p>=0;p--)
            if(anc[nod][p][c] >= lim)
                nod = anc[nod][p][c];
        return nod;
    }
    else
    {
        for(int p=17;p>=0;p--)
            if(anc[nod][p][c] <= lim)
                nod = anc[nod][p][c];
        return nod;
    }
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    n = N;
    for(int i=0;i<X.size();i++)
    {
        con[X[i]].push_back(Y[i]);
        con[Y[i]].push_back(X[i]);
    }
    calc_arb(0);
    calc_arb(1);
    vector<int> sol(L.size(), 0);
    for(int i=0;i<L.size();i++)
    {
        int v1 = get_anc(S[i],1,L[i]);
        int v0 = get_anc(E[i],0,R[i]);
        for(int u=tin[v0][0];u<=tout[v0][0];u++)
        {
            int x = who[u][0];
            if(tin[v1][1] <= tin[x][1] && tin[x][1] <= tout[v1][1])
            {
                sol[i] = 1;
                break;
            }
        }
    }
    return sol;
}

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