Submission #1191526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191526		alexdd	늑대인간 (IOI18_werewolf)	C++20	100 / 100	373 ms	109940 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;
    }
}

int aib[200005];
int qry(int poz)
{
    int aux=0;
    for(int i=poz;i>0;i-=(i&(-i)))
        aux += aib[i];
    return aux;
}
void upd(int poz, int newv)
{
    for(int i=poz;i<=n;i+=(i&(-i)))
        aib[i] += newv;
}

vector<pair<pair<int,int>,pair<int,int>>> qrys;
vector<pair<int,pair<int,int>>> queries[200005];
int sol[200005];


void solve_qrys()
{
    for(auto [x,id]:qrys)
    {
        /*int cnt=0;
        for(int i=0;i<n;i++)
            if(tin[i][0]<=x.first && tin[i][1]<=x.second)
                cnt++;
        sol[id.first] += cnt*id.second;*/
        queries[x.first].push_back({x.second,id});
    }
    for(int i=1;i<=n;i++)
    {
        upd(tin[who[i][0]][1], +1);
        for(auto [x,id]:queries[i])
        {
            sol[id.first] += qry(x)*id.second;
        }
    }
}

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);
    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]);
        qrys.push_back({{tout[v0][0],tout[v1][1]},{i,+1}});
        qrys.push_back({{tout[v0][0],tin[v1][1]-1},{i,-1}});
        qrys.push_back({{tin[v0][0]-1,tout[v1][1]},{i,-1}});
        qrys.push_back({{tin[v0][0]-1,tin[v1][1]-1},{i,+1}});
    }
    solve_qrys();
    vector<int> afis(L.size(),0);
    for(int i=0;i<L.size();i++)
        afis[i] = (sol[i]!=0);
    return afis;
}

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