제출 #1171191

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1171191		mnbvcxz123	Werewolf (IOI18_werewolf)	C++20	100 / 100	615 ms	85008 KiB

werewolf

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

constexpr int N=2e5+5;
vector<int>sons[N<<1];
set<int>nodes[N];
int n;
vector<int>ql[N],qr[N];
vector<int>g[N];
int nod_inter[N];
int st[N<<1],en[N<<1];

struct DSU{
    int par[N<<1];
    int id=0;
    void init(){
        for(int i=0;i<2*n;++i)par[i]=i;
        id=n-1;
    }
    int root(int x){
        if(par[x]==x)return x;
        return par[x]=root(par[x]);
    }
    void unite1(int u, int v){
        u=root(u);
        v=root(v);
        if(u==v)return;
        ++id;
        sons[id].push_back(u);
        sons[id].push_back(v);
        par[u]=par[v]=id;
    }
    void unite2(int u, int v){
        u=root(u);
        v=root(v);
        if(u==v)return;
        if(nodes[u].size()<nodes[v].size())swap(u,v);
        par[v]=u;
        for(auto it:nodes[v])nodes[u].insert(it);
        nodes[v].clear();
    }
}dsu;

void dfs(int v){
    static int tr=0;
    st[v]=tr;
    for(const int&i:sons[v])
        dfs(i);
    if(sons[v].empty())++tr;
    en[v]=tr-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;
    for(int i=0;i<q;++i){
        ql[L[i]].push_back(i);
        qr[R[i]].push_back(i);
    }
    for(int i=0;i<m;++i){
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    dsu.init();
    for(int i=n-1;i>=0;--i){
        for(auto vec:g[i])
            if(vec>i)
                dsu.unite1(i,vec);
        for(auto qry:ql[i])
            nod_inter[qry]=dsu.root(S[qry]);
    }
    dfs(dsu.id);
    dsu.init();
    for(int i=0;i<n;++i)nodes[i].insert(st[i]);
    vector<int>ans(q);
    for(int i=0;i<n;++i){
        for(auto vec:g[i])
            if(vec<i)dsu.unite2(i,vec);
        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() and *it<=en[intv])ans[qry]=1;
            else ans[qry]=0;
        }
    }
    return ans;
}

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