| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 603084 | achibasadzishvili | 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>
#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define maxn 400005
using namespace std;
ll m,n,p[maxn],in1[maxn],out1[maxn],in2[maxn],out2[maxn],ans[maxn];
ll tout1[maxn],tout2[maxn],tin1[maxn],tin2[maxn],s[maxn],t[maxn],l[maxn],r[maxn];
ll P1[200005][19],P2[200005][19],q,was[maxn],pown = 1;
vector<ll>v[maxn],ne[maxn],ol[maxn],be[maxn],ed[maxn];
vector<pair<ll,ll> >g;
ll tt[6000005];
ll timer = 0;
ll find(ll x){
if(p[x] == x)return x;
return p[x] = find(p[x]);
}
void join(ll x,ll y){
x = find(x);
y = find(y);
if(x == y)return;
if(y > x)swap(x,y);
p[y] = x;
}
void join1(ll x,ll y){
x = find(x);
y = find(y);
if(x == y)return;
if(y < x)swap(x , y);
p[y] = x;
}
void dfs(ll x, ll par){
timer++;
in1[x] = timer;
tin1[timer] = x;
P1[x][0] = par;
for(int i=1;i<=18;i++)
P1[x][i] = P1[P1[x][i-1]][i-1];
for(int i=0; i<ne[x].size(); i++)
if(ne[x][i] != par)
dfs(ne[x][i],x);
timer++;
out1[x] = timer;
tout1[timer] = x;
}
void dfs1(ll x,ll par){
timer++;
in2[x] = timer;
tin2[timer] = x;
P2[x][0] = par;
for(int i=1;i<=18;i++)
P2[x][i] = P2[P2[x][i-1]][i-1];
for(int i=0; i<ol[x].size(); i++)
if(ol[x][i] != par)
dfs1(ol[x][i],x);
timer++;
out2[x] = timer;
tout2[timer] = x;
}
ll bigne(ll x,ll y){
for(int i=18; i>=0; i--)
if(P1[x][i])
if(P1[x][i] <= y)
x = P1[x][i];
return x;
}
ll bigol(ll x,ll y){
for(int i=18; i>=0; i--)
if(P2[x][i])
if(P2[x][i] >= y)
x = P2[x][i];
return x;
}
void upd(ll x){
if(!x)return;
tt[x] = tt[2 * x] + tt[2 * x + 1];
upd(x / 2);
}
ll cnt(ll x,ll L,ll R,ll l1,ll r1){
if(L > r1 || R < l1)return 0;
if(L >= l1 && R <= r1)return tt[x];
ll k1 = cnt(2 * x,L , (L + R) / 2 , l1 , r1);
ll k2 = cnt(2 * x + 1,(L + R) / 2 + 1 , R , l1 , r1);
return k1 + k2;
}
int main(){
cin >> n >> m >> q;
while(pown <= 2 * n){
pown *= 2;
}
for(int i=1; i<=m; i++){
ll x,y;
cin >> x >> y;
x++;
y++;
v[x].pb(y);
v[y].pb(x);
g.pb(mp(max(x,y) , min(x,y)));
}
for(int i=1; i<=q; i++){
cin >> s[i] >> t[i] >> l[i] >> r[i];
s[i]++;
t[i]++;
l[i]++;
r[i]++;
}
sort(g.begin(),g.end());
for(int i=1; i<=n; i++){
p[i] = i;
}
for(int i=0; i<g.size(); i++){
ll x,y;
x = g[i].f;
y = g[i].s;
x = find(x);
y = find(y);
if(x != y){
join(x,y);
ne[x].pb(y);
ne[y].pb(x);
}
}
for(int i=0; i<g.size(); i++){
swap(g[i].f , g[i].s);
}
sort(g.begin() , g.end());
reverse(g.begin() , g.end());
for(int i=1; i<=n; i++){
p[i] = i;
}
for(int i=0; i<g.size(); i++){
ll x,y;
x = g[i].f;
y = g[i].s;
x = find(x);
y = find(y);
if(x != y){
join1(x,y);
ol[x].pb(y);
ol[y].pb(x);
}
}
dfs(n,0);
timer = 0;
dfs1(1,0);
for(int i=1; i<=q; i++){
s[i] = bigol(s[i] , l[i]);
t[i] = bigne(t[i] , r[i]);
be[in2[s[i]]].pb(i);
ed[out2[s[i]]].pb(i);
}
for(int i=1; i<=2 * n; i++){
for(int j=0; j<be[i].size(); j++)
was[be[i][j]] = cnt(1,1,pown,in1[t[be[i][j]]] , out1[t[be[i][j]]]);
if(tin2[i] != 0){
tt[pown + in1[tin2[i]] - 1]++;
upd((pown + in1[tin2[i]] - 1) / 2);
}
for(int j=0; j < ed[i].size(); j++){
ll now = cnt(1,1,pown,in1[t[ed[i][j]]] , out1[t[ed[i][j]]] );
if(now > was[ed[i][j]])
ans[ed[i][j]] = 1;
}
}
for(int i=1; i<=q; i++)
cout << ans[i] << endl;
return 0;
}