oj.uz

Submission #314496

# Submission time Handle Problem Language Result Execution time Memory
314496 2020-10-20T05:25:44 Z juggernaut Werewolf (IOI18_werewolf) C++14
34 / 100
 921 ms 51828 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 > 0) {
                        int md = (hi + lo+1) >> 1;
                        if (check(pos[E[i]+1],md,1,e)) lo = md;
                        else hi = md-1;
                  }
                 // if (check(pos[E[i]+1],hi,1,e)) lo = hi;

                  l = pos[E[i]+1],r = pos[S[i]+1];
                  while (r - l > 0) {
                        int md = (r + l) >> 1;
                        if (check(pos[S[i]+1],md,s,n)) r = md;
                        else l = md+1;
                  }
                  //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 808 ms 51696 KB Output is correct
2 Correct 910 ms 51696 KB Output is correct
3 Correct 921 ms 51824 KB Output is correct
4 Correct 918 ms 51696 KB Output is correct
5 Correct 910 ms 51760 KB Output is correct
6 Correct 852 ms 51652 KB Output is correct
7 Correct 848 ms 51668 KB Output is correct
8 Correct 896 ms 51672 KB Output is correct
9 Correct 560 ms 51596 KB Output is correct
10 Correct 531 ms 51828 KB Output is correct
11 Correct 547 ms 51696 KB Output is correct
12 Correct 559 ms 51700 KB Output is correct
13 Correct 877 ms 51732 KB Output is correct
14 Correct 882 ms 51696 KB Output is correct
15 Correct 862 ms 51624 KB Output is correct
16 Correct 860 ms 51756 KB Output is correct
17 Correct 851 ms 51696 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 -