Submission #314799

#	Time	Username	Problem	Language	Result	Execution time	Memory
314799		amunduzbaev	Werewolf (IOI18_werewolf)	C++14	0 / 100	736 ms	524292 KiB

werewolf

//#include "grader.cpp"
#include "werewolf.h"
#include <bits/stdc++.h>
#define pb(n) push_back(n)
using namespace std;
const int N= 2*1e5+5;
vector<vector<int>>edges;
//2nd 1st subtask

struct first{
    bool reached=0;
    int l, h, used1[N],used2[N];
    void dfs1(int v){
        used1[v]=1;
        for(auto x:edges[v]){
            if(x<l||used1[x]) continue;
            dfs1(x);
        }
    }
    void dfs2(int v){
        used2[v]=1;
        if(used1[v]&&used2[v]) {
            reached=1;
            return;
        }
        if(reached) return;
        for(auto x:edges[v]){
            if(x>h||used2[x]) continue;
            if(reached) return;
            dfs2(x);
        }
    }
};


// 3rd subtask
const int INF=1e9+7;
int root, timer, n, m, q;
vector<int>a(N);
void dfs(int u,int p){
    a[u]=timer, timer++;
    for(auto x:edges[u]){
        if(x == p) continue;
        dfs(x, u);
    }
}
struct second{
    struct node{
        int mx,mn;
    };
    vector<node>tree;
    int s;
    node ntr={0,INF};
    void mtree(int n){
        s=1;
        while(s<n) s*=2;
        tree.assign(s*2, ntr);
        for(int i=0;i<n;i++)
            tree[a[i]+s]={i, i};
        for(int i=s-1;i>0;i--){
            tree[i].mn=min(tree[i*2+1].mn, tree[i*2].mn);
            tree[i].mx=max(tree[i*2+1].mx, tree[i*2].mx);
        }
    }
    int min_less(int l,int r,int lx,int rx,int x,int low){
        if(lx>=r||rx<=l) return INF;
        if(lx==rx){
            if(lx>=l&&tree[x].mn<low) return lx;
            else return INF;
        }
        int mid=(lx+rx)/2;
        if(lx>=l&&rx<=r){
            if(tree[x*2].mn<low) return min_less(l,r,lx,mid,x*2,low);
            else return min_less(l,r,mid+1,rx,x*2+1,low);
        }return min(min_less(l,r,lx,mid,x*2,low),
                    min_less(l,r,mid+1,rx,x*2+1,low));
    }
    int min_less1(int l,int low){
        return min_less(l, s, 0, s, 1, low);
    }
    int min_great(int l,int r,int lx,int rx,int x,int low){
        if(lx>=r||rx<=l) return INF;
        if(lx==rx){
            if(lx>=l&&tree[x].mn>low) return lx;
            else return INF;
        }
        int mid=(lx+rx)/2;
        if(lx>=l&&rx<=r){
            if(tree[x*2].mn>low) return min_great(l,r,lx,mid,x*2,low);
            else return min_great(l,r,mid+1,rx,x*2+1,low);
        }return min(min_great(l,r,lx,mid,x*2,low),
                    min_great(l,r,mid+1,rx,x*2+1,low));
    }

    int min_great1(int l,int low){
        return min_great(l,s,0,s,1,low);
    }

//======================================================================================================

    int max_less(int l,int r,int lx,int rx,int x,int high){
        if(lx>=r||rx<=l) return -1;
        if(rx==lx){
            if(rx<=r && tree[x].mx<high) return lx;
            else return -1;
        }
        int mid=(lx+rx)/2;
        if(lx>=l&&rx<=r){
            if(tree[x*2+1].mx<high) return max_less(l,r,mid+1,rx,x*2+1,high);
            else return max_less(l,r,lx,mid,x*2,high);
        }
        return max(max_less(l,r,lx,mid,x*2,high), max_less(l,r,mid+1,rx,x*2+1,high));
    }
    int max_less1(int r,int high){
        return max_less(0,r,0,s,0,high);
    }
    int max_great(int l,int r,int lx,int rx,int x,int high){
        if(lx>=r||rx<=l) return -1;
        if(rx==lx){
            if(rx<=r && tree[x].mx<high) return lx;
            else return -1;
        }
        int mid=(lx+rx)/2;
        if(lx>=l&&rx<=r){
            if(tree[x*2+1].mx<high) return max_great(l,r,mid+1,rx,x*2+1,high);
            else return max_great(l,r,lx,mid,x*2,high);
        }
        return max(max_great(l,r,lx,mid,x*2,high), max_less(l,r,mid+1,rx,x*2+1,high));
    }
    int max_great1(int r,int high){
        return max_great(0,r,0,s,0,high);
    }
};


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,q=S.size(),m=X.size();
    edges.resize(n);
    for(int i=0;i<m;i++){
        edges[X[i]].pb(Y[i]);
        edges[Y[i]].pb(X[i]);
    }

    if(n<3000){
        first ans;
        a.resize(q);
        for(int i=0;i<q;i++){
            ans.l=l[i], ans.h=l[i];
            if(S[i]>=ans.l)
            ans.dfs1(S[i]);
            ans.reached=0;
            if(E[i]<=ans.h)
            ans.dfs2(E[i]);
            a[i]=ans.reached;
            memset(ans.used1,0,sizeof(ans.used1));
            memset(ans.used2,0,sizeof(ans.used2));
        }
        return a;
    }

    for(int i=1;i<=n;i++)
        if(edges[i].size()==1) root = i;
    timer=0;
    dfs(root, root);
    second stree;
    stree.mtree(n);
    vector<int>ans(q);
    for(int i=0;i<q;i++){
        int s=a[S[i]],e=a[E[i]];
        ans[i]=1;
        if(s<e){
            int mnlt_L=stree.min_less1(s,l[i])-1,
            mxgt_R=stree.max_great1(e,r[i])+1;
            if(mnlt_L<mxgt_R) ans[i]=0;
        }else{
            int mxlt_L=stree.max_less1(s,l[i])+1;
            int mngt_R=stree.min_great1(e,r[i])-1;
            if(mxlt_L > mngt_R)ans[i]=0;
        }
    }
    return ans;
}

/*

    6 5 3
    1 2
    2 3
    3 4
    4 5
    0 1
    1 3 4 5
    1 3 4 5
    3 2 4 4

*/

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