oj.uz

Submission #420485

# Submission time Handle Problem Language Result Execution time Memory
420485 2021-06-08T11:47:42 Z A_D Werewolf (IOI18_werewolf) C++14
34 / 100
 1187 ms 73412 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;




        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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 40 ms 43284 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 40 ms 43284 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 994 ms 65640 KB Output is correct
2 Correct 1033 ms 73360 KB Output is correct
3 Correct 1094 ms 73300 KB Output is correct
4 Correct 1077 ms 73288 KB Output is correct
5 Correct 1102 ms 73244 KB Output is correct
6 Correct 1006 ms 73228 KB Output is correct
7 Correct 1085 ms 73172 KB Output is correct
8 Correct 965 ms 73192 KB Output is correct
9 Correct 535 ms 73196 KB Output is correct
10 Correct 574 ms 73176 KB Output is correct
11 Correct 709 ms 73232 KB Output is correct
12 Correct 587 ms 73352 KB Output is correct
13 Correct 1131 ms 73380 KB Output is correct
14 Correct 1160 ms 73276 KB Output is correct
15 Correct 1121 ms 73368 KB Output is correct
16 Correct 1187 ms 73272 KB Output is correct
17 Correct 1055 ms 73412 KB Output is correct

Subtask #4
0 / 51.0

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