oj.uz

Submission #314494

# Submission time Handle Problem Language Result Execution time Memory
314494 2020-10-20T05:19:52 Z juggernaut Werewolf (IOI18_werewolf) C++14
34 / 100
 1085 ms 51996 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){
    if(l>r)swap(l,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){
    if(l>r)swap(l,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 (gt_mx(pos[E[i]+1],md) <= e) lo = md;
                        else hi = md;
                  }
                  if (gt_mx(pos[E[i]+1],hi) <= e) lo = hi;

                  l = pos[E[i]+1],r = pos[S[i]+1];
                  while (r - l > 1) {
                        int md = (r + l) >> 1;
                        if (gt_mn(md,pos[S[i]+1]) >= s) r = md;
                        else l = md;
                  }
                  if (gt_mn(l,pos[S[i]+1]) >= s) 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:111:1: warning: "/*" within comment [-Wcomment]
  111 | /*
      |  
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:26:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(i=0;i<x.size();i++){
      |             ~^~~~~~~~~
werewolf.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=0;i<S.size();i++){
      |                 ~^~~~~~~~~
werewolf.cpp:33:14: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   33 |     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 967 ms 51568 KB Output is correct
2 Correct 1067 ms 51696 KB Output is correct
3 Correct 1077 ms 51696 KB Output is correct
4 Correct 1068 ms 51952 KB Output is correct
5 Correct 1085 ms 51824 KB Output is correct
6 Correct 1033 ms 51952 KB Output is correct
7 Correct 932 ms 51696 KB Output is correct
8 Correct 1037 ms 51952 KB Output is correct
9 Correct 580 ms 51696 KB Output is correct
10 Correct 528 ms 51696 KB Output is correct
11 Correct 571 ms 51696 KB Output is correct
12 Correct 567 ms 51824 KB Output is correct
13 Correct 967 ms 51708 KB Output is correct
14 Correct 963 ms 51996 KB Output is correct
15 Correct 958 ms 51824 KB Output is correct
16 Correct 967 ms 51696 KB Output is correct
17 Correct 934 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 -