oj.uz

Submission #805442

# Submission time Handle Problem Language Result Execution time Memory
805442 2023-08-03T16:41:37 Z Khizri Werewolf (IOI18_werewolf) C++17
15 / 100
 588 ms 130236 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=2e5+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 8 ms 14512 KB Output is correct
2 Correct 7 ms 14444 KB Output is correct
3 Correct 7 ms 14436 KB Output is correct
4 Correct 6 ms 14396 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 7 ms 14516 KB Output is correct
7 Correct 6 ms 14548 KB Output is correct
8 Correct 7 ms 14420 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14512 KB Output is correct
2 Correct 7 ms 14444 KB Output is correct
3 Correct 7 ms 14436 KB Output is correct
4 Correct 6 ms 14396 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 7 ms 14516 KB Output is correct
7 Correct 6 ms 14548 KB Output is correct
8 Correct 7 ms 14420 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 11 ms 16084 KB Output is correct
11 Correct 12 ms 16104 KB Output is correct
12 Correct 11 ms 16144 KB Output is correct
13 Correct 11 ms 16212 KB Output is correct
14 Correct 12 ms 16204 KB Output is correct
15 Correct 12 ms 16212 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 588 ms 130236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14512 KB Output is correct
2 Correct 7 ms 14444 KB Output is correct
3 Correct 7 ms 14436 KB Output is correct
4 Correct 6 ms 14396 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 7 ms 14516 KB Output is correct
7 Correct 6 ms 14548 KB Output is correct
8 Correct 7 ms 14420 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 11 ms 16084 KB Output is correct
11 Correct 12 ms 16104 KB Output is correct
12 Correct 11 ms 16144 KB Output is correct
13 Correct 11 ms 16212 KB Output is correct
14 Correct 12 ms 16204 KB Output is correct
15 Correct 12 ms 16212 KB Output is correct
16 Incorrect 588 ms 130236 KB Output isn't correct
17 Halted 0 ms 0 KB -