Submission #139174

#	Time	Username	Problem	Language	Result	Execution time	Memory
139174		Hassoony	Werewolf (IOI18_werewolf)	C++17	34 / 100	1932 ms	524292 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
//#include "grader.cpp"
using namespace std;
const int MX=4e5+9;
int n,in[MX],timer,org[MX],seg[MX*5],seg1[MX*5],ind[MX*5],indright[MX*5];
vector<int>v[MX];
void dfs(int x,int p){
    in[x]=++timer;
    org[timer]=x;
    for(auto pp:v[x]){
        if(pp==p)continue;
        dfs(pp,x);
    }
}
void build(int node,int l,int r){
    if(l == r){
        seg[node] = org[l];
        ind[node] = indright[node] = l;
        return;
    }
    int mid=(l+r)/2;
    build(node*2,l,mid);
    build(node*2+1,mid+1,r);

    seg[node]=min(seg[node*2],seg[node*2+1]);

    if(seg[node*2] < seg[node*2+1]) ind[node] = ind[node*2];
    else ind[node] = ind[node*2+1];

    if(seg[node*2] <= seg[node*2+1]) indright[node] = indright[node*2];
    else indright[node] = indright[node*2+1];
}
pair<int,int> q(int node,int l,int r,int s,int e,bool ok){
    if(l > e || r < s)return {MX,-1};
    if(l >= s && r <= e){
        if(ok == 0)return {seg[node],ind[node]};
        return {seg[node],indright[node]};
    }
    int mid=(l+r)/2;
    pair<int,int> p1=q(node*2,l,mid,s,e,ok);
    pair<int,int> p2=q(node*2+1,mid+1,r,s,e,ok);
    if(ok == 0){
        if(p1.first < p2.first) return p1;
        else return p2;
    }
    else{
        if(p1.first <= p2.first) return p1;
        else return p2;
    }
}


void build1(int node,int l,int r){
    if(l == r){
        seg1[node] = org[l];
        return;
    }
    int mid=(l+r)/2;
    build1(node*2,l,mid);
    build1(node*2+1,mid+1,r);
    seg1[node]=max(seg1[node*2],seg1[node*2+1]);
}
int q1(int node,int l,int r,int s,int e){
    if(l > e || r < s)return -1;
    if(l >= s && r <= e)return seg1[node];
    int mid=(l+r)/2;
    return max(q1(node*2,l,mid,s,e),q1(node*2+1,mid+1,r,s,e));
}


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;
    for(int i=0;i<X.size();i++){
        v[X[i]].push_back(Y[i]);
        v[Y[i]].push_back(X[i]);
    }
    int root=0;
    for(int i=0;i<n;i++){
        if(v[i].size() == 1){
            root = i;
        }
    }
    dfs(root,-1);
    build(1,1,n);
    build1(1,1,n);
    vector<int>res;
    for(int i=0;i<S.size();i++){
        int s=S[i],e=E[i];
        if(s == e){
            if(s >= L[i] && s <= R[i])res.push_back(1);
            else res.push_back(0);
        }
        if(in[s] > in[e]){
            int r=in[s],l=in[e];
            int ans=-1;
            while(l<=r){
                int mid=(l+r)/2;
                if(q(1,1,n,mid,in[s],1).first >= L[i]){
                    ans=mid;
                    r=mid-1;
                }
                else l=mid+1;
            }
            if(ans == -1){
                res.push_back(0);
                continue;
            }
            if(q1(1,1,n,in[e],ans) > R[i]){
                res.push_back(0);
            }
            else res.push_back(1);
            continue;
        }
        int l=in[s],r=in[e];
        int ans=-1;
        while(l<=r){
            int mid=(l+r)/2;
            if(q(1,1,n,in[s],mid,0).first >= L[i]){
                ans=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        if(ans == -1){
            res.push_back(0);
            continue;
        }
        if(q1(1,1,n,ans,in[e]) > R[i]){
            res.push_back(0);
        }
        else res.push_back(1);
    }
    return res;
}
/*
10 9 7
3 9
9 1
1 0
0 4
4 2
2 5
5 6
6 8
8 10
3 8 1 8
4 9 3 10
3 5 3 8
2 8 1 10
8 4 7 9
4 6 3 5
6 4 3 5
*/

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:76:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<X.size();i++){
                 ~^~~~~~~~~
werewolf.cpp:90:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<S.size();i++){
                 ~^~~~~~~~~

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