| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 142806 | LittleFlowers__ | 늑대인간 (IOI18_werewolf) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(false),cin.tie(nullptr);
#define task "werewolf"
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
int cnt,cur;
int fre[100010];
vector<int> ad[100010];
void add(int u,queue<int>&q){
q.push(u);
cnt=cnt||fre[u]+1==cur&&!(cur&1);
fre[u]=cur;
}
void bfs(int s,int l,int r){
cur++; queue<int> q; add(s,q);
while(q.size()){
int u=q.front(); q.pop();
forv(v,ad[u]) if(l<=v && v<=r && fre[v]<cur) add(v,q);
}
}
vector<int> check_validity(int n, vector<int>x, vector<int>y, vector<int>s, vector<int>t, vector<int>l, vector<int>r){
int m=x[i].size();
forinc(i,0,m-1){
ad[x[i]].pb(y[i]);
ad[y[i]].pb(x[i]);
}
int q=s.size();
vector<int> ret;
forinc(i,0,q-1){
if(s[i]<l[i] || t[i]>r[i]){
ret.pb(0);
continue;
}
cnt=0;
bfs(t[i],0,r[i]);
bfs(s[i],l[i],n-1);
ret.pb(cnt);
}
return ret;
}