Submission #1052243

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052243		Ahmed57	Werewolf (IOI18_werewolf)	C++17	100 / 100	580 ms	188476 KiB

werewolf

#include "bits/stdc++.h"

using namespace std;
int pr[600001];
int sp[600001];
int val1[600001];
int val2[600001];
vector<int> MI[600001];
vector<int> MA[600001];
int find(int x){
    if(x==pr[x])return x;
    return pr[x] = find(pr[x]);
}
bool mergegroup(int a,int b){
    a = find(a) , b = find(b);
    if(a==b)return 0;
    pr[a] = b;
    return 1;
}
int P[600001][20][2];
int timer = 0;
int in[600001][2];
int out[600001][2];
void dfs1(int i,int pr){
    P[i][0][0] = pr;
    in[i][0] = ++timer;
    for(int j = 1;j<20;j++){
        P[i][j][0] = P[P[i][j-1][0]][j-1][0];
    }
    for(auto j:MI[i]){
        if(j==pr)continue;
        dfs1(j,i);
    }
    out[i][0] = timer;
}
int rev[600001];
int n,m,q;
void dfs2(int i,int pr){
    in[i][1] = ++timer;
    if(i<n)rev[timer] = i;
    else rev[timer] = -1;
    P[i][0][1] = pr;
    for(int j = 1;j<20;j++){
        P[i][j][1] = P[P[i][j-1][1]][j-1][1];
    }
    for(auto j:MA[i]){
        if(j==pr)continue;
        dfs2(j,i);
    }
    out[i][1] = timer;
}
int seg[2400001];
void build(int p,int l,int r){
    seg[p] = 1e9;
    if(l==r)return ;
    int md = (l+r)/2;
    build(p*2,l,md);
    build(p*2+1,md+1,r);
}
void update(int p,int l,int r,int idx,int val){
    if(l==r){
        seg[p] = val;
        return ;
    }
    int md = (l+r)/2;
    if(idx<=md)update(p*2,l,md,idx,val);
    else update(p*2+1,md+1,r,idx,val);
    seg[p] = min(seg[p*2],seg[p*2+1]);
}
int query(int p,int l,int r,int lq,int rq){
    if(l>=lq&&r<=rq)return seg[p];
    if(r<lq||l>rq)return 1e9;
    int md = (l+r)/2;
    return min(query(p*2,l,md,lq,rq),query(p*2+1,md+1,r,lq,rq));
}
vector<int> check_validity(int N,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> L,vector<int> R){
    m = X.size();
    q = L.size();
    n = N;
    vector<array<int,3>> mi,ma;
    for(int i = 0;i<m;i++){
        mi.push_back({max(X[i],Y[i]),X[i],Y[i]});
        ma.push_back({min(X[i],Y[i]),X[i],Y[i]});
    }
    sort(mi.begin(),mi.end());
    sort(ma.begin(),ma.end());
    reverse(ma.begin(),ma.end());
    for(int i = 0;i<n;i++){
        pr[i] = i;
        sp[i] = i;
        val1[i] = i;
    }
    int nc = n;
    for(auto i:mi){
        if(find(i[1])==find(i[2]))continue;
        int A = find(i[1]);
        int B = find(i[2]);
        MI[nc].push_back(sp[A]);
        MI[nc].push_back(sp[B]);
        val1[nc] = i[0];
        mergegroup(i[1],i[2]);
        sp[find(i[1])] = nc;
        nc++;
    }
    for(int i = 0;i<n;i++){
        pr[i] = i;
        sp[i] = i;
        val2[i] = i;
    }
    nc = n;
    for(auto i:ma){
        if(find(i[1])==find(i[2]))continue;
        int A = find(i[1]);
        int B = find(i[2]);
        MA[nc].push_back(sp[A]);
        MA[nc].push_back(sp[B]);
        val2[nc] = i[0];
        mergegroup(i[1],i[2]);
        sp[find(i[1])] = nc;
        nc++;
    }
    timer = 0;
    dfs1(nc-1,nc-1);
    int nah = timer;
    timer = 0;
    dfs2(nc-1,nc-1);
    vector<array<int,4>> rngs[600001];
    for(int i = 0;i<q;i++){
        for(int j = 19;j>=0;j--){
            if(val2[P[S[i]][j][1]]>=L[i]){
                S[i] = P[S[i]][j][1];
            }
        }
        for(int j = 19;j>=0;j--){
            if(val1[P[E[i]][j][0]]<=R[i]){
                E[i] = P[E[i]][j][0];
            }
        }
        rngs[in[S[i]][1]].push_back({out[S[i]][1],in[E[i]][0],out[E[i]][0],i});
    }
    build(1,1,timer);
    vector<int> ANS(q,0);
    for(int i = timer;i>=1;i--){
        if(rev[i]!=-1){
            int no = rev[i];
            update(1,1,timer,in[no][0],i);
        }
        for(auto j:rngs[i]){
            if(query(1,1,timer,j[1],j[2])<=j[0]){
                ANS[j[3]] = 1;
            }else ANS[j[3]] = 0;
        }
    }
    return ANS;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:124:9: warning: unused variable 'nah' [-Wunused-variable]
  124 |     int nah = timer;
      |         ^~~

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51