oj.uz

Submission #314493

# Submission time Handle Problem Language Result Execution time Memory
314493 2020-10-20T05:15:50 Z juggernaut Werewolf (IOI18_werewolf) C++14
34 / 100
 2291 ms 64344 KB 
#include"werewolf.h"
#include<bits/stdc++.h>
//#include"grader.cpp"
#define V vector




#define node pair<int,int>
#define a first
#define b second




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;
}






node t[200005 * 4],cr;
node combine(node a,node b) {
      a.a = max(a.a,b.a);
      a.b = min(a.b,b.b);
      return a;
}
void build (int v ,int tl,int tr) {
      if (tl == tr) {
            t[v].a = t[v].b = spx[tl][0];
      }
      else {
            int tm = (tl + tr) >> 1;
            build (v + v,tl,tm);
            build (v + v + 1,tm + 1,tr);
            t[v] = combine(t[v + v],t[v + v + 1]);
      }
}
node get (int l,int r,int v ,int tl ,int tr ) {
      if (tl > r || tr < l) return {0,2e9};
      if (l <= tl && tr <= r) return t[v];
      int tm = (tl + tr) >> 1;
      return combine(get(l,r,v + v,tl,tm),get(l,r,v + v + 1,tm + 1,tr));
}







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]);
    }
    build(1,1,n);
    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;
                        cr = get(pos[E[i]+1],md,1,1,n);
                        if (cr.a <= e) lo = md;
                        else hi = md;
                  }
                  cr = get(pos[E[i]+1],hi,1,1,n);
                  if (cr.a <= e) lo = hi;

                  l = pos[E[i]+1],r = pos[S[i]+1];
                  while (r - l > 1) {
                        int md = (r + l) >> 1;
                        cr = get(md,pos[S[i]+1],1,1,n);
                        if (cr.b >= s) r = md;
                        else l = md;
                  }
                  cr = get(l,pos[S[i]+1],1,1,n);

                  if (cr.b >= 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:162:1: warning: "/*" within comment [-Wcomment]
  162 | /*
      |  
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:71:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(i=0;i<x.size();i++){
      |             ~^~~~~~~~~
werewolf.cpp:99:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for(int i=0;i<S.size();i++){
      |                 ~^~~~~~~~~
werewolf.cpp:78:14: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |     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 1959 ms 55860 KB Output is correct
2 Correct 2288 ms 64284 KB Output is correct
3 Correct 2291 ms 64220 KB Output is correct
4 Correct 2213 ms 64240 KB Output is correct
5 Correct 2169 ms 64152 KB Output is correct
6 Correct 2045 ms 64168 KB Output is correct
7 Correct 2041 ms 64112 KB Output is correct
8 Correct 2222 ms 64112 KB Output is correct
9 Correct 979 ms 64112 KB Output is correct
10 Correct 1087 ms 64160 KB Output is correct
11 Correct 1229 ms 64240 KB Output is correct
12 Correct 1450 ms 64288 KB Output is correct
13 Correct 2074 ms 64192 KB Output is correct
14 Correct 2067 ms 64344 KB Output is correct
15 Correct 2080 ms 64192 KB Output is correct
16 Correct 2086 ms 64288 KB Output is correct
17 Correct 2069 ms 64272 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 -