Submission #138907

#	Time	Username	Problem	Language	Result	Execution time	Memory
138907		Hassoony	Werewolf (IOI18_werewolf)	C++17	0 / 100	1710 ms	524292 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
//#include "grader.cpp"
using namespace std;
const int MX=2e5+9;
int n,in[MX],timer,org[MX],seg[MX*5],seg1[MX*5],ind[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] = 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];
}
pair<int,int> q(int node,int l,int r,int s,int e){
    if(l > e || r < s)return {MX,-1};
    if(l >= s && r <= e)return {seg[node],ind[node]};
    int mid=(l+r)/2;
    pair<int,int> p1=q(node*2,l,mid,s,e);
    pair<int,int> p2=q(node*2+1,mid+1,r,s,e);

    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(in[s] > in[e])swap(s,e);
        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).first >= L[i]){
                ans=q(1,1,n,in[s],mid).second;
                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;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/

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:65:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<X.size();i++){
                 ~^~~~~~~~~
werewolf.cpp:77: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: 0 / 34
• Subtask 4: 0 / 51