oj.uz

Submission #314495

# Submission time Handle Problem Language Result Execution time Memory
314495 2020-10-20T05:22:12 Z juggernaut Werewolf (IOI18_werewolf) C++14
34 / 100
 1115 ms 51808 KB 
#include"werewolf.h"
#include<bits/stdc++.h>
//#include"grader.cpp"
#define V vector
using namespace std;
V<int>g[200005];
int pos[200005],logs[200005],spx[200005][18],spn[200005][18];
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){
    if(l>r)swap(l,r);
    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>>1]+1;
    V<int>res;
    for(i=0;i<x.size();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;
    spx[1][0]=root;
    spn[1][0]=root;
    pos[root]=1;
    int p=root;
    for(i=2;i<=n;i++){
        if(g[root][0]!=p){
            p=root;
            root=g[root][0];
        }else{
            p=root;
            root=g[root][1];
        }
        spx[i][0]=root;
        spn[i][0]=root;
        pos[root]=i;
    }
    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]+1,e=R[i]+1;
        if(l<=r){
            int mxl=n,mnr=1;
            while(l<mxl){
                int mid=(l+mxl+1)>>1;
                if(check(pos[S[i]+1],mid,s,n))l=mid;
                else mxl=mid-1;
            }
            while(mnr<r){
                int mid=(mnr+r)>>1;
                if(check(mid,pos[E[i]+1],1,e))r=mid;
                else mnr=mid+1;
            }
            res.push_back(mxl>=mnr);
        }else{
            int lo = r,hi = l;
                  while (hi - lo > 1) {
                        int md = (hi + lo) >> 1;
                        if (check(pos[E[i]+1],md,1,e)) lo = md;
                        else hi = md;
                  }
                  if (check(pos[E[i]+1],hi,1,e)) lo = hi;

                  l = pos[E[i]+1],r = pos[S[i]+1];
                  while (r - l > 1) {
                        int md = (r + l) >> 1;
                        if (check(pos[S[i]+1],md,s,n)) r = md;
                        else l = md;
                  }
                  if (check(pos[S[i]+1],l,s,n)) r = l;
                  res.push_back(r <= lo);
        }
    }
    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

/*
1
1
1
0
1
1
0
1
0
1

*/

Compilation message

werewolf.cpp:109:1: warning: "/*" within comment [-Wcomment]
  109 | /*
      |  
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:24:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(i=0;i<x.size();i++){
      |             ~^~~~~~~~~
werewolf.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i=0;i<S.size();i++){
      |                 ~^~~~~~~~~
werewolf.cpp:31:14: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |     spx[1][0]=root;
      |     ~~~~~~~~~^~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 9984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 9984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 909 ms 51568 KB Output is correct
2 Correct 1087 ms 51568 KB Output is correct
3 Correct 1115 ms 51568 KB Output is correct
4 Correct 1073 ms 51572 KB Output is correct
5 Correct 1041 ms 51568 KB Output is correct
6 Correct 956 ms 51572 KB Output is correct
7 Correct 944 ms 51636 KB Output is correct
8 Correct 1041 ms 51568 KB Output is correct
9 Correct 576 ms 51568 KB Output is correct
10 Correct 542 ms 51764 KB Output is correct
11 Correct 584 ms 51744 KB Output is correct
12 Correct 571 ms 51568 KB Output is correct
13 Correct 997 ms 51568 KB Output is correct
14 Correct 982 ms 51568 KB Output is correct
15 Correct 994 ms 51700 KB Output is correct
16 Correct 1012 ms 51740 KB Output is correct
17 Correct 939 ms 51808 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 9984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -