Submission #314210

#	Time	Username	Problem	Language	Result	Execution time	Memory
314210		juggernaut	Werewolf (IOI18_werewolf)	C++14	0 / 100	486 ms	121212 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,i,j;
    for(i=2;i<=n;i++)logs[i]=logs[i/2]+1;
    V<int>res;
    for(i=0;i+1<n;i++){
        x[i]++;
        y[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 l=pos[S[i]+1],r=pos[E[i]+1],s=L[i],e=R[i];
        if(l>r)swap(l,r);
        int mxl=n,mnr=1;
        while(l<mxl){
            int mid=(l+mxl+1)>>1;
            if(check(L[i],mid,s,n))l=mid;
            else mxl=mid-1;
        }
        while(mnr<r){
            int mid=(mnr+r)>>1;
            if(check(mid,R[i],1,e))r=mid;
            else mnr=mid+1;
        }
        res.push_back(mxl>=mnr);
    }
    return res;
}
/*
10 9 10
6 7
1 5
8 0
2 9
9 4
2 7
8 5
6 0
3 4
4 9 0 9
8 1 8 9
1 8 1 8
8 3 5 5
8 9 3 9
0 1 0 2
9 0 6 6
1 7 1 8
9 4 5 6
9 5 0 9

*/

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:41:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i=0;i<S.size();i++){
      |                 ~^~~~~~~~~
werewolf.cpp:36:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   36 |     run(root,root);
      |     ~~~^~~~~~~~~~~

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