| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 600885 | enerelt14 | 늑대인간 (IOI18_werewolf) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "werewolf.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
struct node{
int mn, mx;
node(){
mn=mx=0;
}
}
bool vis[3005], is[3005];
vector<int>adj[3005];
void dijkstra1(int s, int l){
queue<int>pq;
pq.push(s);
while(!pq.empty()){
int u=pq.front();
pq.pop();
vis[u]=1;
for (int i=0;i<adj[u].size();i++){
if (adj[u][i]<l || vis[adj[u][i]])continue;
pq.push(adj[u][i]);
}
while(!pq.empty() && vis[pq.front()])pq.pop();
}
}
void dijkstra2(int s, int r){
queue<int>pq;
pq.push(s);
while(!pq.empty()){
int u=pq.front();
pq.pop();
vis[u]=1;
for (int i=0;i<adj[u].size();i++){
if (adj[u][i]>r || vis[adj[u][i]])continue;
pq.push(adj[u][i]);
}
while(!pq.empty() && vis[pq.front()])pq.pop();
}
}
int x[200005], num[200005], pos[200005];
node tree[800005];
void build(int id, int l, int r){
if (l==r){
tree[id].mn=x[l];
tree[id].mx=x[l];
return;
}
int mid=(l+r)/2;
build(id*2+1, l, mid);
build(id*2+2, mid+1, r);
tree[id].mn=min(tree[id*2+1].mn, tree[id*2+2].mn);
tree[id].mx=max(tree[id*2+1].mx, tree[id*2+2].mx);
}
int querymn(int id, int l, int r, int L, int R){
if (L>r || l>R)return INT_MAX;
if (L<=l && r<=R)return tree[id].mn;
int mid=(l+r)/2;
return min(querymn(id*2+1, l, mid, L, R), querymn(id*2+2, mid+1, r, L, R));
}
int querymx(int id, int l, int r, int L, int R){
if (L>r || l>R)return 0;
if (L<=l && r<=R)return tree[id].mx;
int mid=(l+r)/2;
return max(querymx(id*2+1, l, mid, L, R), querymx(id*2+2, mid+1, r, L, R));
}
vector<int>check_validity(int N,vector<int>X,vector<int>Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R){
if (N<=3000 && X.size()<=6000 && S.size()<=3000){
for (int i=0;i<X.size();i++){
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
int Q=S.size();
vector<int>ans;
for (int j=0;j<Q;j++){
ans.pb(0);
if (S[j]<L[j] || E[j]>R[j])continue;
for (int i=L[j];i<N;i++)vis[i]=0;
dijkstra1(S[j], L[j]);
for (int i=L[j];i<=R[j];i++)is[i]=vis[i];
for (int i=0;i<=R[j];i++)vis[i]=0;
dijkstra2(E[j], R[j]);
for (int i=L[j];i<=R[j];i++){
if (vis[i] && is[i]){
ans[j]=1;
break;
}
}
}
return ans;
}
for (int i=0;i<X.size();i++){
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
x[0]=N;
for (int i=0;i<N;i++){
if (adj[i].size()==1){
x[1]=i;
break;
}
}
for (int i=2;i<=N;i++){
if (adj[x[i-1]][0]==x[i-2])x[i]=adj[x[i-1]][1];
else x[i]=adj[x[i-1]][0];
}
for (int i=1;i<=N;i++)pos[x[i]]=i;
build(0, 1, N);
vector<int>ans;
for (int i=0;i<S.size();i++){
ans.pb(0);
if (S[i]<L[i] && E[i]>R[i])continue;
if (pos[S[i]]==pos[E[i]]){
ans[i]=1;
continue;
}
if (pos[S[i]]>pos[E[i]]){
int l=1, r=pos[S[i]];
while(l!=r){
int mid=(l+r)/2;
if (querymn(0, 1, N, mid, r)>=L[i])r=mid;
else l=mid+1;
}
if (l<=pos[E[i]] || querymx(pos[E[i]], l)<=R[i])ans[i]=1;
}else{
int l=pos[S[i]], r=N;
while(l!=r){
int mid=(l+r)/2;
if (querymn(0, 1, N, l, mid+1)>=L[i])l=mid+1;
else r=mid;
}
if (l>=pos[E[i]] || querymx(l, pos[E[i]])<=R[i])ans[i]=1;
}
}
return ans;
}