Submission #1006572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006572		irmuun	Werewolf (IOI18_werewolf)	C++17	0 / 100	1049 ms	524288 KiB

werewolf

#include<bits/stdc++.h>
#include "werewolf.h"
 
using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

struct segtreeMax{
    int n;
    vector<int>d;
    segtreeMax(int n):n(n){
        d.resize(4*n);
        build(1,0,n-1);
    }
    void build(int node,int l,int r){
        if(l==r){
            d[node]=0;
            return;
        }
        int mid=(l+r)/2;
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
    }
    int query(int node,int l,int r,int L,int R){
        if(L>R||l>R||L>r) return 0;
        if(L<=l&&r<=R) return d[node];
        int mid=(l+r)/2;
        return max(query(node*2,l,mid,L,R),query(node*2+1,mid+1,r,L,R));
    }
    void update(int node,int l,int r,int pos,int val){
        if(r<pos||pos<l) return;
        if(l==r){
            d[node]=val;
            return;
        }
        int mid=(l+r)/2;
        update(node*2,l,mid,pos,val);
        update(node*2+1,mid+1,r,pos,val);
        d[node]=max(d[node*2],d[node*2+1]);
    }
};

struct segtreeMin{
    int n;
    vector<int>d;
    segtreeMin(int n):n(n){
        d.resize(4*n);
        build(1,0,n-1);
    }
    void build(int node,int l,int r){
        if(l==r){
            d[node]=0;
            return;
        }
        int mid=(l+r)/2;
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
    }
    int query(int node,int l,int r,int L,int R){
        if(L>R||l>R||L>r) return n;
        if(L<=l&&r<=R) return d[node];
        int mid=(l+r)/2;
        return min(query(node*2,l,mid,L,R),query(node*2+1,mid+1,r,L,R));
    }
    void update(int node,int l,int r,int pos,int val){
        if(r<pos||pos<l) return;
        if(l==r){
            d[node]=val;
            return;
        }
        int mid=(l+r)/2;
        update(node*2,l,mid,pos,val);
        update(node*2+1,mid+1,r,pos,val);
        d[node]=min(d[node*2],d[node*2+1]);
    }
};
 
vector<int>check_validity(int N,vector<int>X,vector<int>Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R){
    int Q=S.size();
    int n=N;
    vector<int>can(Q,0);
    vector<int>adj[N];
    for(int i=0;i<X.size();i++){
        adj[X[i]].pb(Y[i]);
        adj[Y[i]].pb(X[i]);
    }
    vector<int>pos(N);
    int cur=0;
    segtreeMax sgmx(N);
    segtreeMin sgmn(N);
    function <void(int,int)> dfs=[&](int x,int p){
        sgmx.update(1,0,n-1,cur,x);
        sgmn.update(1,0,n-1,cur,x);
        pos[x]=cur;
        cur++;
        for(int y:adj[x]){
            if(y!=p){
                dfs(y,x);
            }
        }
    };
    for(int i=0;i<N;i++){
        if(adj[i].size()==1){
            dfs(i,-1);
            break;
        }
    }
    for(int i=0;i<Q;i++){
        if(pos[E[i]]<=pos[S[i]]){
            int l=pos[E[i]],r=n-1,x,y;
            while(l<r){
                int mid=(l+r+1)/2;
                if(sgmn.query(1,0,n-1,pos[E[i]],mid)>=L[i]){
                    l=mid;
                }
                else{
                    r=mid-1;
                }
            }
            x=l;
            l=0,r=pos[S[i]];
            while(l<r){
                int mid=(l+r)/2;
                if(sgmx.query(1,0,n-1,mid,pos[S[i]])<=R[i]){
                    r=mid;
                }
                else{
                    l=mid+1;
                }
            }
            y=l;
            can[i]=(x>=y);
        }
        else{
            int l=pos[S[i]],r=n-1,x,y;
            while(l<r){
                int mid=(l+r+1)/2;
                if(sgmx.query(1,0,n-1,pos[S[i]],mid)<=R[i]){
                    l=mid;
                }
                else{
                    r=mid-1;
                }
            }
            x=l;
            l=0,r=pos[E[i]];
            while(l<r){
                int mid=(l+r)/2;
                if(sgmn.query(1,0,n-1,mid,pos[S[i]])>=L[i]){
                    r=mid;
                }
                else{
                    l=mid+1;
                }
            }
            y=l;
            can[i]=(x>=y);
        }
    }
    return can;
}

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:88:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int i=0;i<X.size();i++){
      |                 ~^~~~~~~~~

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