Submission #420485

#	Time	Username	Problem	Language	Result	Execution time	Memory
420485		A_D	Werewolf (IOI18_werewolf)	C++14	34 / 100	1187 ms	73412 KiB

werewolf

#include "werewolf.h"

#include <bits/stdc++.h>

using namespace std;
const int N=2e5+100;
const int Le=20;
int mn[N][Le];
int mx[N][Le];
vector<int> g[N];
int idx[N];
int n;
int cnt=0;
int a[N];
int lo[N];
void dfs(int u,int p)
{
    a[cnt]=u;
    idx[u]=cnt;
    cnt++;
    for(auto x:g[u]){
        if(x==p)continue;
        dfs(x,u);
    }
}
int getmn(int L,int R)
{
    int j=lo[R-L+1];
    int ret=min(mn[L][j],mn[R-(1<<j)+1][j]);
    return ret;
}
int getmx(int L,int R)
{
    int j=lo[R-L+1];
    int ret=max(mx[L][j],mx[R-(1<<j)+1][j]);
    return ret;
}
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;
    lo[1]=0;
    for(int i=2;i<=n+100;i++){
        lo[i]=lo[i/2]+1;
    }
    for(int i=0;i<n-1;i++){
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    for(int i=0;i<N;i++){
        if(g[i].size()==1){
            dfs(i,i);
            break;
        }
    }
    for(int i=0;i<n;i++){
        mn[i][0]=a[i];
        mx[i][0]=a[i];
    }
    for(int j=1;j<Le;j++){
        for(int i=0;i+(1<<j)<=n;i++){
            mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
            mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
        }
    }
    vector<int> ret;
    for(int t=0;t<S.size();t++){
        int a=idx[S[t]];
        int b=idx[E[t]];
//        cout<<a<<" "<<b<<endl;




        int l=a,r=n-1,r1;
        while(l<=r){
            int mid=(l+r)/2;
            if(getmn(a,mid)>=L[t]){
                l=mid+1;
                r1=mid;
            }
            else{
                r=mid-1;
            }
        }
        l=0,r=a;
        int l1;
        while(l<=r){
            int mid=(l+r)/2;
            if(getmn(mid,a)>=L[t]){
                r=mid-1;
                l1=mid;
            }
            else{
                l=mid+1;
            }
        }

        l=b,r=n-1;
        int r2;
        while(l<=r){
            int mid=(l+r)/2;
//            cout<<b<<" "<<mid<<" "<<getmx(b,mid)<<endl;
            if(getmx(b,mid)<=R[t]){
                l=mid+1;
                r2=mid;
            }
            else{
                r=mid-1;
            }
        }
        l=0,r=b;
        int l2;
        while(l<=r){
            int mid=(l+r)/2;
            if(getmx(mid,b)<=R[t]){
                r=mid-1;
                l2=mid;
            }
            else{
                l=mid+1;
            }
        }
//        cout<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<endl;
        ret.push_back(max(l1,l2)<=min(r1,r2));
    }
    return ret;
}


/*
9 8 1
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8

9 8 1
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
7 2 4 4


6 5 1
3 2
2 4
4 1
1 0
0 5



6 5 1
3 2
2 4
4 1
1 0
0 5
0 2 0 1
*/

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 of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int t=0;t<S.size();t++){
      |                 ~^~~~~~~~~
werewolf.cpp:111:13: warning: 'l2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  111 |         int l2;
      |             ^~
werewolf.cpp:98:13: warning: 'r2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |         int r2;
      |             ^~
werewolf.cpp:85:13: warning: 'l1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |         int l1;
      |             ^~
werewolf.cpp:73:23: warning: 'r1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |         int l=a,r=n-1,r1;
      |                       ^~

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