oj.uz

Submission #420463

# Submission time Handle Problem Language Result Execution time Memory
420463 2021-06-08T11:33:38 Z A_D Werewolf (IOI18_werewolf) C++14
0 / 100
 634 ms 67908 KB 
#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;
        if(a<L[t]||b>R[t]){
            ret.push_back(0);
            continue;
        }




        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

*/

Compilation message

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:115:13: warning: 'l2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  115 |         int l2;
      |             ^~
werewolf.cpp:102:13: warning: 'r2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  102 |         int r2;
      |             ^~
werewolf.cpp:89:13: warning: 'l1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   89 |         int l1;
      |             ^~
werewolf.cpp:77:23: warning: 'r1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |         int l=a,r=n-1,r1;
      |                       ^~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 43204 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 43204 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 634 ms 67908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 43204 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -