Submission #1163318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163318		AlgorithmWarrior	Werewolf (IOI18_werewolf)	C++20	0 / 100	442 ms	589824 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"

using namespace std;

int const MAX=4e5+5;
vector<int>sons[MAX];
set<int>nodes[MAX];
int n;
vector<int>qL[MAX],qR[MAX];
vector<int>G[MAX];
int nod_inter[MAX];
int st[MAX],dr[MAX];

struct DSU{
    int tata[MAX];
    int id;
    void init(){
        int i;
        for(i=0;i<n;++i)
            tata[i]=i;
        id=n-1;
    }
    int root(int nod){
        if(tata[nod]==nod)
            return nod;
        return tata[nod]=root(tata[nod]);
    }
    void uneste1(int u,int v){
        u=root(u);
        v=root(v);
        if(u!=v){
            ++id;
            sons[id].push_back(u);
            sons[id].push_back(v);
            tata[u]=id;
            tata[v]=id;
        }
    }
    void uneste2(int u,int v){
        u=root(u);
        v=root(v);
        if(u!=v){
            if(nodes[u].size()<nodes[v].size())
                swap(u,v);
            tata[v]=u;
            for(auto elem : nodes[v])
                nodes[u].insert(elem);
            nodes[v].clear();
        }
    }
}dsu;

void dfs(int nod){
    static int time=0;
    st[nod]=time;
    for(auto fiu : sons[nod])
        dfs(fiu);
    if(sons[nod].empty())
        ++time;
    dr[nod]=time-1;
}

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 q = S.size();
    int m=X.size();
    n=N;
    int i;
    for(i=0;i<q;++i){
        qL[L[i]].push_back(i);
        qR[R[i]].push_back(i);
    }
    for(i=0;i<m;++i){
        G[X[i]].push_back(Y[i]);
        G[Y[i]].push_back(X[i]);
    }
    dsu.init();
    for(i=n-1;i>=0;--i){
        for(auto vec : G[i])
            if(vec>i)
                dsu.uneste1(i,vec);
        for(auto qry : qL[i])
            nod_inter[qry]=dsu.root(S[qry]);
    }
    dfs(dsu.id);
    dsu.init();
    for(i=0;i<n;++i)
        nodes[i].insert(st[i]);
    vector<int>ans(q);
    for(i=0;i<n;++i){
        for(auto vec : G[i])
            if(vec<i)
                dsu.uneste2(vec,i);
        for(auto qry : qR[i]){
            int pos=E[qry];
            int rt=dsu.root(pos);
            int intv=nod_inter[qry];
            auto it=nodes[rt].lower_bound(st[intv]);
            if(it!=nodes[rt].end() && *it<=dr[intv])
                ans[qry]=1;
            else
                ans[qry]=0;
        }
    }
    return ans;
}

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