oj.uz

Submission #805458

# Submission time Handle Problem Language Result Execution time Memory
805458 2023-08-03T16:47:30 Z Khizri Werewolf (IOI18_werewolf) C++17
100 / 100
 1114 ms 276172 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=2e6+5;
int n,m,q,tmm,nxt=1,mn[mxn],mx[mxn],p[mxn],sz[mxn],idx[mxn],idx2[mxn],l[mxn],r[mxn],l2[mxn],r2[mxn],L[mxn*20],R[mxn*20],room[mxn],tree[mxn*20],par[mxn][20],par2[mxn][20];
vector<int>vt[mxn];
vector<int>vtx[mxn],vty[mxn];
void build(int node,int l,int r){
    if(l==r) return;
    L[node]=++nxt;
    R[node]=++nxt;
    int m=(l+r)/2;
    build(L[node],l,m);
    build(R[node],m+1,r);
}
int update(int node,int l,int r,int pos){
    int nw=++nxt;
    if(l==r){
        tree[nw]=1;
        return nw;
    }
    int m=(l+r)/2;
    L[nw]=L[node],R[nw]=R[node];
    if(pos<=m){
        L[nw]=update(L[nw],l,m,pos);
    }
    else{
        R[nw]=update(R[nw],m+1,r,pos);
    }
    tree[nw]=tree[L[nw]]+tree[R[nw]];
    return nw;
}
int query(int node,int node2,int l,int r,int ql,int qr){
    if(l>qr||r<ql){
        return 0;
    }
    if(ql<=l&&r<=qr){
        return tree[node]-tree[node2];
    }
    int m=(l+r)/2;
    return query(L[node],L[node2],l,m,ql,qr)+query(R[node],R[node2],m+1,r,ql,qr);
}
void dfs(int u,int p){
    par[u][0]=p;
    l[u]=++tmm;
    idx[tmm]=u;
    for(int v:vtx[u]){
        if(v!=p){
            dfs(v,u);
        }
    }
    r[u]=tmm;
}
void dfs2(int u,int p){
    par2[u][0]=p;
    l2[u]=++tmm;
    idx2[tmm]=u;
    for(int v:vty[u]){
        if(v!=p){
            dfs2(v,u);
        }
    }
    r2[u]=tmm;
}
int fnd(int u){
    if(p[u]==u) return u;
    return p[u]=fnd(p[u]);
}
void Union(int u,int v){
    u=fnd(u);
    v=fnd(v);
    if(u!=v){
        if(sz[v]>sz[u]) swap(u,v);
        sz[u]+=sz[v];
        p[v]=u;
        mn[u]=min(mn[u],mn[v]);
        mx[u]=max(mx[u],mx[v]);
    }
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> lx,vector<int> rx) {
    q = S.size();
    n=N;
    m=X.size();
    for(int i=0;i<m;i++){
        int u=X[i]+1,v=Y[i]+1;
        vt[u].pb(v);
        vt[v].pb(u);
    }
    for(int i=1;i<=n;i++){
        p[i]=i;
        sz[i]=1;
        mx[i]=i;
        mn[i]=i;
    }
    for(int i=n;i>=1;i--){
        int u=i;
        for(int v:vt[u]){
            if(v>u&&fnd(u)!=fnd(v)){
                int nw=mn[fnd(v)];
                vtx[u].pb(nw);
                vtx[nw].pb(u);
                Union(u,nw);
            }
        }
    }
    for(int i=1;i<=n;i++){
        p[i]=i;
        sz[i]=1;
        mx[i]=i;
        mn[i]=i;
    }
    for(int i=1;i<=n;i++){
        int u=i;
        for(int v:vt[u]){
            if(v<u&&fnd(v)!=fnd(u)){
                int nw=mx[fnd(v)];
                vty[u].pb(nw);
                vty[nw].pb(u);
                Union(u,nw);
            }
        }
    }
    tmm=0;
    dfs(1,-1);
    par[1][0]=1;
    tmm=0;
    dfs2(n,-1);
    par2[n][0]=n;
    for(int j=1;j<20;j++){
        for(int i=1;i<=n;i++){
            par[i][j]=par[par[i][j-1]][j-1];
            par2[i][j]=par2[par2[i][j-1]][j-1];
        }
    }
    build(1,1,n);
    room[0]=1;
    for(int i=1;i<=n;i++){
        int a=idx2[i];
        int pos=l[a];
        room[i]=update(room[i-1],1,n,pos);
    }
    vector<int>ans;
    for(int i=0;i<q;i++){
        int u=S[i]+1,v=E[i]+1,a=lx[i],b=rx[i];
        for(int j=19;j>=0;j--){
            if(par[u][j]-1>=a){
                u=par[u][j];
            }
            if(par2[v][j]-1<=b){
                v=par2[v][j];
            }
        }
        if(query(room[r2[v]],room[l2[v]-1],1,n,l[u],r[u])>0){
            ans.pb(1);
        }
        else{
            ans.pb(0);
        }
    }
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 141356 KB Output is correct
2 Correct 59 ms 141356 KB Output is correct
3 Correct 60 ms 141276 KB Output is correct
4 Correct 59 ms 141308 KB Output is correct
5 Correct 60 ms 141272 KB Output is correct
6 Correct 59 ms 141356 KB Output is correct
7 Correct 59 ms 141264 KB Output is correct
8 Correct 58 ms 141304 KB Output is correct
9 Correct 59 ms 141352 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 141356 KB Output is correct
2 Correct 59 ms 141356 KB Output is correct
3 Correct 60 ms 141276 KB Output is correct
4 Correct 59 ms 141308 KB Output is correct
5 Correct 60 ms 141272 KB Output is correct
6 Correct 59 ms 141356 KB Output is correct
7 Correct 59 ms 141264 KB Output is correct
8 Correct 58 ms 141304 KB Output is correct
9 Correct 59 ms 141352 KB Output is correct
10 Correct 63 ms 142824 KB Output is correct
11 Correct 64 ms 142796 KB Output is correct
12 Correct 63 ms 142796 KB Output is correct
13 Correct 64 ms 143000 KB Output is correct
14 Correct 64 ms 142928 KB Output is correct
15 Correct 64 ms 142896 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 257708 KB Output is correct
2 Correct 778 ms 269492 KB Output is correct
3 Correct 664 ms 267116 KB Output is correct
4 Correct 559 ms 266208 KB Output is correct
5 Correct 649 ms 266252 KB Output is correct
6 Correct 620 ms 266048 KB Output is correct
7 Correct 558 ms 266040 KB Output is correct
8 Correct 735 ms 269392 KB Output is correct
9 Correct 505 ms 267092 KB Output is correct
10 Correct 457 ms 266232 KB Output is correct
11 Correct 482 ms 266096 KB Output is correct
12 Correct 460 ms 266104 KB Output is correct
13 Correct 744 ms 270748 KB Output is correct
14 Correct 740 ms 270700 KB Output is correct
15 Correct 714 ms 270728 KB Output is correct
16 Correct 732 ms 270880 KB Output is correct
17 Correct 550 ms 265972 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 141356 KB Output is correct
2 Correct 59 ms 141356 KB Output is correct
3 Correct 60 ms 141276 KB Output is correct
4 Correct 59 ms 141308 KB Output is correct
5 Correct 60 ms 141272 KB Output is correct
6 Correct 59 ms 141356 KB Output is correct
7 Correct 59 ms 141264 KB Output is correct
8 Correct 58 ms 141304 KB Output is correct
9 Correct 59 ms 141352 KB Output is correct
10 Correct 63 ms 142824 KB Output is correct
11 Correct 64 ms 142796 KB Output is correct
12 Correct 63 ms 142796 KB Output is correct
13 Correct 64 ms 143000 KB Output is correct
14 Correct 64 ms 142928 KB Output is correct
15 Correct 64 ms 142896 KB Output is correct
16 Correct 626 ms 257708 KB Output is correct
17 Correct 778 ms 269492 KB Output is correct
18 Correct 664 ms 267116 KB Output is correct
19 Correct 559 ms 266208 KB Output is correct
20 Correct 649 ms 266252 KB Output is correct
21 Correct 620 ms 266048 KB Output is correct
22 Correct 558 ms 266040 KB Output is correct
23 Correct 735 ms 269392 KB Output is correct
24 Correct 505 ms 267092 KB Output is correct
25 Correct 457 ms 266232 KB Output is correct
26 Correct 482 ms 266096 KB Output is correct
27 Correct 460 ms 266104 KB Output is correct
28 Correct 744 ms 270748 KB Output is correct
29 Correct 740 ms 270700 KB Output is correct
30 Correct 714 ms 270728 KB Output is correct
31 Correct 732 ms 270880 KB Output is correct
32 Correct 550 ms 265972 KB Output is correct
33 Correct 923 ms 267396 KB Output is correct
34 Correct 261 ms 173520 KB Output is correct
35 Correct 1114 ms 269804 KB Output is correct
36 Correct 790 ms 266632 KB Output is correct
37 Correct 1038 ms 269012 KB Output is correct
38 Correct 885 ms 267236 KB Output is correct
39 Correct 915 ms 275900 KB Output is correct
40 Correct 678 ms 275432 KB Output is correct
41 Correct 807 ms 268512 KB Output is correct
42 Correct 494 ms 266692 KB Output is correct
43 Correct 1067 ms 273656 KB Output is correct
44 Correct 976 ms 268964 KB Output is correct
45 Correct 789 ms 276172 KB Output is correct
46 Correct 943 ms 275908 KB Output is correct
47 Correct 726 ms 270864 KB Output is correct
48 Correct 713 ms 270676 KB Output is correct
49 Correct 729 ms 270872 KB Output is correct
50 Correct 744 ms 270668 KB Output is correct
51 Correct 608 ms 275956 KB Output is correct
52 Correct 587 ms 276056 KB Output is correct