Submission #314201

#	Time	Username	Problem	Language	Result	Execution time	Memory
314201		juggernaut	Werewolf (IOI18_werewolf)	C++14	0 / 100	644 ms	92024 KiB

werewolf

#include"werewolf.h"
#include<bits/stdc++.h>
//#include"grader.cpp"
#define V vector
using namespace std;
V<int>g[200005];
int order,pos[200005],logs[200005],spx[200005][18],spn[200005][18];
void run(int v,int p){
    spx[++order][0]=v;
    spn[order][0]=v;
    pos[v]=order;
    for(int to:g[v])if(to!=p)run(to,v);
}
int gt_mx(int l,int r){
    int lev=logs[r-l+1];
    return max(spx[l][lev],spx[r-(1<<lev)+1][lev]);
}
int gt_mn(int l,int r){
    int lev=logs[r-l+1];
    return min(spn[l][lev],spn[r-(1<<lev)+1][lev]);
}
bool check(int l,int r,int nl,int nr){
    return gt_mn(l,r)>=nl&&gt_mx(l,r)<=nr;
}
V<int>check_validity(int n,V<int>x,V<int>y,V<int>S,V<int>E,V<int>L,V<int>R){
    int root=0,i,j;
    for(i=2;i<=n;i++)logs[i]=logs[i/2]+1;
    V<int>res;
    for(i=1;i<n;i++){
        g[x[i]].push_back(y[i]);
        g[y[i]].push_back(x[i]);
    }
    for(i=1;i<=n;i++)if(g[i].size()==1)root=i;
    run(root,root);
    for(j=1;j<18;j++){
        for(i=1;i+(1<<j)-1<=n;i++)spn[i][j]=min(spn[i][j-1],spn[i+(1<<(j-1))][j-1]);
        for(i=1;i+(1<<j)-1<=n;i++)spx[i][j]=max(spx[i][j-1],spx[i+(1<<(j-1))][j-1]);
    }
    for(int i=0;i<S.size();i++){
        int s=pos[S[i]],e=pos[E[i]],l=L[i],r=R[i];
        int mxl=n,mnr=1;
        while(l<mxl){
            int mid=(l+mxl+1)>>1;
            if(check(L[i],mid,L[i],n))l=mid;
            else mxl=mid-1;
        }
        while(mnr<r){
            int mid=(mnr+r)>>1;
            if(check(mid,R[i],1,R[i]))r=mid;
            else mnr=mid+1;
        }
        res.push_back(mxl>=mnr);
    }
    return res;
}

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:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i=0;i<S.size();i++){
      |                 ~^~~~~~~~~
werewolf.cpp:40:13: warning: unused variable 's' [-Wunused-variable]
   40 |         int s=pos[S[i]],e=pos[E[i]],l=L[i],r=R[i];
      |             ^
werewolf.cpp:40:25: warning: unused variable 'e' [-Wunused-variable]
   40 |         int s=pos[S[i]],e=pos[E[i]],l=L[i],r=R[i];
      |                         ^

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