oj.uz

Submission #314498

# Submission time Handle Problem Language Result Execution time Memory
314498 2020-10-20T05:33:15 Z juggernaut Werewolf (IOI18_werewolf) C++14
34 / 100
 894 ms 51824 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{
//            swap(l,r);
//            r=n;
//            while(l<r){
//                int mid=(l+r+1)>>1;
//                if(check(pos[E[i]+1],mid,1,e))l=mid;
//                else r=mid-1;
//            }
//            int tmp=l;
//            l=pos[E[i]+1],r=pos[S[i]+1];
//            while(l<r){
//                int mid=(r+l)>>1;
//                if(check(pos[S[i]+1],mid,s,n))r=mid;
//                else l=mid+1;
//            }
//            res.push_back(r<=tmp);
            swap(l,r);
            int mxl=n,mnr=1;
            while(l<mxl){
                int mid=(l+mxl+1)>>1;
                if(check(pos[E[i]+1],mid,1,e))l=mid;
                else mxl=mid-1;
            }
            while(mnr<r){
                int mid=(mnr+r)>>1;
                if(check(mid,pos[S[i]+1],s,n))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

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

*/

Compilation message

werewolf.cpp:121:1: warning: "/*" within comment [-Wcomment]
  121 | /*
      |  
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 843 ms 51568 KB Output is correct
2 Correct 855 ms 51696 KB Output is correct
3 Correct 890 ms 51568 KB Output is correct
4 Correct 881 ms 51764 KB Output is correct
5 Correct 894 ms 51824 KB Output is correct
6 Correct 863 ms 51696 KB Output is correct
7 Correct 873 ms 51700 KB Output is correct
8 Correct 777 ms 51568 KB Output is correct
9 Correct 572 ms 51824 KB Output is correct
10 Correct 537 ms 51568 KB Output is correct
11 Correct 573 ms 51568 KB Output is correct
12 Correct 547 ms 51568 KB Output is correct
13 Correct 868 ms 51636 KB Output is correct
14 Correct 880 ms 51748 KB Output is correct
15 Correct 878 ms 51696 KB Output is correct
16 Correct 863 ms 51696 KB Output is correct
17 Correct 868 ms 51824 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 -