제출 #173423

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

werewolf

#include "werewolf.h"
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;

struct query{
    int s,e;
    int l,r;
    int index;

    query(int a,int b,int c,int d,int _index){
        s=a,e=b,l=c,r=d;
        index=_index;
    }
};

int n,m,q;
vector<int> al[200005];
vector<iii> edges;
vector<query*> __q;

///for kruskal tree
ii range[400005];
int lchild[400005];
int rchild[400005];
int edgew[400005];
int parent[400005][20];

int __IDX;
int __LEAFY;

struct UFDS{
    int p[400005];
    int r[400005];

    UFDS(){
        for (int x=0;x<400005;x++){
            p[x]=x;
            r[x]=0;
        }
    }

    int parent(int i){return (p[i]==i)?i:p[i]=parent(p[i]);}

    void unions(int i,int j,int k){
        i=parent(i),j=parent(j);
        if (i==j) return;
        p[i]=__IDX;
        p[j]=__IDX;
        lchild[__IDX]=i;
        rchild[__IDX]=j;
        edgew[__IDX]=k;
        __IDX++;
    }
}*dsu=new UFDS();

void dfs(int i){
    if (i<n){
        range[i]=ii(__LEAFY,__LEAFY);
        __LEAFY++;
        return;
    }
    int curr;
    curr=parent[lchild[i]][0]=i;
    for (int x=0;parent[curr][x]!=-1;x++){
        curr=parent[lchild[i]][x+1]=parent[curr][x];
    }
    dfs(lchild[i]);
    curr=parent[rchild[i]][0]=i;
    for (int x=0;parent[curr][x]!=-1;x++){
        curr=parent[rchild[i]][x+1]=parent[curr][x];
    }
    dfs(rchild[i]);
    range[i]=ii(range[lchild[i]].first,range[rchild[i]].second);
}

set<int> components[200005];
int pos[200005];
int fin[200005];
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,m=X.size(),q=S.size();

    for (int x=0;x<m;x++){
        edges.push_back(iii(min(X[x],Y[x]),ii(X[x],Y[x])));
    }

    sort(edges.begin(),edges.end());
    reverse(edges.begin(),edges.end());

    __IDX=n;
    __LEAFY=0;
    for (auto &it:edges){
        dsu->unions(it.second.first,it.second.second,it.first);
    }

    memset(parent,-1,sizeof(parent));
    dfs(__IDX-1);

    edges.clear();
    for (int x=0;x<m;x++){
        edges.push_back(iii(max(X[x],Y[x]),ii(range[X[x]].first,range[Y[x]].first)));
    }
    sort(edges.begin(),edges.end());
    reverse(edges.begin(),edges.end());

    for (int x=0;x<n;x++){
        components[x].insert(x);
        pos[x]=x;
    }

    for (int x=0;x<q;x++){
        __q.push_back(new query(S[x],E[x],L[x],R[x],x));
    }
    sort (__q.begin(),__q.end(),[](query *i,query *j){
       return i->r<j->r;
    });

    int s,e,l,r;
    int i,j;
    set<int>::iterator __it;
    for (int x=0;x<q;x++){
        s=__q[x]->s,e=__q[x]->e,l=__q[x]->l,r=__q[x]->r;

        while (!edges.empty() && edges.back().first<=r){
            i=edges.back().second.first,j=edges.back().second.second;
            edges.pop_back();
            if (pos[i]==pos[j]) continue;
            if (components[pos[i]].size()>components[pos[j]].size()) swap(i,j);
            for (auto &it:components[pos[i]]){
                pos[it]=pos[j];
                components[pos[j]].insert(it);
            }
        }

        for (int x=19;~x;x--){
            if (parent[s][x]!=-1 && edgew[parent[s][x]]>=l) s=parent[s][x];
        }

        i=range[s].first,j=range[s].second;
        e=range[e].first;
        __it=components[pos[e]].lower_bound(i);
        if (__it!=components[pos[e]].end() && (*__it)<=j) fin[__q[x]->index]=1;
        else fin[__q[x]->index]=0;
    }

    vector<int> ans;
    for (int x=0;x<q;x++){
        ans.push_back(fin[x]);
    }

    return ans;
}

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