Submission #432173

#	Time	Username	Problem	Language	Result	Execution time	Memory
432173		MDario	Werewolf (IOI18_werewolf)	C++11	0 / 100	720 ms	524292 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
int p1[200001][19], p2[200001][19], l1[200000], r1[200000], l2[200000], r2[200000], st[400001], n;
vector<int> v[200001], t1[200001], t2[200001], et1, et2;
void dfs1(int xf){
    l1[xf]=et1.size();
    et1.push_back(xf);
    for(auto i : t1[xf])dfs1(i);
    r1[xf]=et1.size()-1;
    return;
}
void dfs2(int xf){
    l2[xf]=et2.size();
    et2.push_back(xf);
    for(auto i : t2[xf])dfs2(i);
    r2[xf]=et2.size()-1;
    return;
}
void update(int xf, int yf){
    xf+=n;
    st[xf]=yf;
    xf/=2;
    while(xf>0){
        st[xf]=max(st[xf*2], st[xf*2+1]);
        xf/=2;
    }
    return;
}
int query(int lf, int rf){
    int yf=0;
    while(lf<=rf){
        if(lf&1){
            yf=max(yf, st[lf]);
            lf++;
        }
        if((rf+1)&1){
            yf=max(yf, st[rf]);
            rf--;
        }
        lf/=2;
        rf/=2;
    }
    return yf;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    n=N;
    int q = S.size(), m=X.size();
    vector<int> s(q);
    for(int i=0; i<m; i++){
        v[X[i]].push_back(Y[i]);
        v[Y[i]].push_back(X[i]);
    }
    for(int i=0; i<n; i++){
        p1[i][0]=i;
        p2[i][0]=i;
        sort(v[i].begin(), v[i].end());
    }
    int c=0;
    for(int i=n-1; i>=0; i--){
        c=i;
        for(auto t : v[i]){
            if(t>c){
                p2[c][0]=t;
                c=t;
            }
        }
    }
    for(int i=n-1; i>=0; i--){
        t2[p2[i][0]].push_back(i);
        for(int t=1; t<19; t++)p2[i][t]=p2[p1[i][t-1]][t-1];
    }
    for(int i=0; i<n; i++){
        reverse(v[i].begin(), v[i].end());
    }
    for(int i=0; i<n; i++){
        c=i;
        for(auto t : v[i]){
            if(t<c){
                p1[c][0]=t;
                c=t;
            }
        }
    }
    for(int i=0; i<n; i++){
        t1[p1[i][0]].push_back(i);
        for(int t=1; t<19; t++)p1[i][t]=p1[p1[i][t-1]][t-1];
    }
    dfs1(0);
    dfs2(n-1);
    vector<pair<pair<int, bool>, int>> Q;
    for(int i=0; i<q; i++){
        for(int t=18; t>=0; t--){
            if(p1[S[i]][t]>=L[i])S[i]=p1[S[i]][t];
        }
        Q.push_back({{l1[S[i]], 0}, i});
        Q.push_back({{r1[S[i]], 1}, i});
    }
    for(int i=0; i<q; i++){
        for(int t=18; t>=0; t--){
            if(p2[E[i]][t]<=R[i])E[i]=p2[E[i]][t];
        }
    }
    c=0;
    int c1=0, c2, c3;
    sort(Q.begin(), Q.end());
    for(int i=0; i<2*q; i++){
        while(c1<Q[i].F.F){
            update(et1[c1], c);
            c1++;
        }
        if(Q[i].F.S){
            c2=l2[R[Q[i].S]];
            c3=r2[R[Q[i].S]];
            if(query(c2, c3)>=s[Q[i].S])s[Q[i].S]=1;
            else s[Q[i].S]=0;
        }
        else{
            c++;
            s[Q[i].S]=c;
        }
    }
    return s;
}

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