| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 173341 | errorgorn | 늑대인간 (IOI18_werewolf) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 __LEAF;
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(__LEAF,__LEAF);
__LEAF++;
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;
__LEAF=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;
__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;
}