| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 283537 | peti1234 | Werewolf (IOI18_werewolf) | C++17 | 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>
using namespace std;
using vi=vector<int>;
#define rep(n) for (int i=0; i<n; i++)
const int c=200002;
int m, q, hely[c], mini[c][20], maxi[c][20], cnt;
vi sz[c], sol;
bool kis[c], nagy[c], v[c], jo;
void kdfs(int a, int b) {
kis[a]=1;
rep(sz[a].size()) {
int x=sz[a][i];
if (!kis[x] && x<=b) kdfs(x, b);
}
}
void ndfs(int a, int b) {
nagy[a]=1;
rep(sz[a].size()) {
int x=sz[a][i];
if (!nagy[x] && x>=b) ndfs(x, b);
}
}
void dfs(int a) {
v[a]=true, mini[cnt][0]=a, maxi[cnt][0]=a, hely[a]=cnt, cnt++;
rep(sz[a].size()) {
int x=sz[a][i];
if (!v[x]) dfs(x);
}
}
vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r) {
m=x.size(), q=s.size();
rep(m) sz[x[i]].push_back(y[i]), sz[y[i]].push_back(x[i]);
if (n<=3000 && q<=3000) {
rep(q) {
jo=0;
rep(n) kis[i]=0, nagy[i]=0;
kdfs(e[i], r[i]);
ndfs(s[i], l[i]);
rep(n) if (kis[i] && nagy[i]) jo=1;
sol.push_back(jo);
}
return sol;
}
rep(n) if (!v[i] && sz[i].size()==1) dfs(i);
for (int j=1; j<20; j++) rep(n) {
int p=min(n-1, i+(1<<(j-1)));
mini[i][j]=min(mini[i][j-1], mini[p][j-1]);
maxi[i][j]=max(maxi[i][j-1], maxi[p][j-1]);
}
rep(q) {
int em=hely[s[i]], fa=hely[e[i]];
if (em<fa) {
for (int j=19; j>=0; j--) if (em<n && mini[em][j]>=l[i]) em+=(1<<j);
for (int j=19; j>=0; j--) {
int x=max(0, fa-(1<<j)+1);
if (maxi[x][j]<=r[i]) fa=x-1;
}
sol.push_back((em>=n || fa==-1 || em-fa>1));
} else {
for (int j=19; j>=0; j--) if (fa<n && maxi[fa][j]<=r[i]) fa+=(1<<j);
for (int j=19; j>=0; j--) {
int x=max(0, em-(1<<j)+1);
if (mini[x][j]>=l[i]) em=x-1;
}
sol.push_back((fa>=n || em==-1 || fa-em>1));
}
}
return sol;
}
int b1, b2, b3;
vi v1, v2, v3, v4, v5, v6, v7;
int main()
{
cin >> b1 >> b2 >> b3;
rep(b2) {
int a; cin >> a;
v1.push_back(a);
}
rep(b2) {
int a; cin >> a;
v2.push_back(a);
}
rep(b3) {
int a; cin >> a;
v3.push_back(a);
}
rep(b3) {
int a; cin >> a;
v4.push_back(a);
}
rep(b3) {
int a; cin >> a;
v5.push_back(a);
}
rep(b3) {
int a; cin >> a;
v6.push_back(a);
}
v7=check_validity(b1, v1, v2, v3, v4, v5, v6);
rep(b3) cout << v7[i] << " ";
return 0;
}