oj.uz

Submission #116294

# Submission time Handle Problem Language Result Execution time Memory
116294 2019-06-12T04:05:02 Z mirbek01 Werewolf (IOI18_werewolf) C++11
34 / 100
 852 ms 69004 KB 
# include <bits/stdc++.h>
# include "werewolf.h"

using namespace std;

const int N = 4e5 + 2;

int ver[N], pos[N], n, t[2][18][N], lg[N];
vector <int> g[N];

int get(int l, int r, int tp){
      int curlog = lg[r - l + 1];
      if(tp)
            return max(t[1][curlog][l], t[1][curlog][r - (1 << curlog) + 1]);
      else
            return min(t[0][curlog][l], t[0][curlog][r - (1 << curlog) + 1]);
}

void dfs(int v, int par = -1){
      ver[++ n] = v;
      for(int to : g[v]){
            if(to == par)
                  continue;
            dfs(to, v);
      }
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
      int q = S.size();
      int m = X.size();
      vector <int> A(q);

      for(int i = 0; i < m; i ++){
            g[X[i]].push_back(Y[i]);
            g[Y[i]].push_back(X[i]);
      }

      for(int i = 0; i < N; i ++){
            if(g[i].size() == 1){
                  dfs(i);
                  break;
            }
      }

      for(int i = 1; i <= n; i ++){
            pos[ver[i]] = i;
      }

      for(int i = 2; i <= n; i ++)
            lg[i] = lg[i / 2] + 1;

      for(int i = 0; i <= lg[n]; i ++){
            if(!i){
                  for(int j = 1; j <= n; j ++)
                        t[0][i][j] = ver[j],
                        t[1][i][j] = ver[j];
            } else {
                  int curlen = 1 << (i - 1);
                  for(int j = 1; j <= n; j ++){
                        t[0][i][j] = min(t[0][i - 1][j], t[0][i - 1][min(n, j + curlen)]),
                        t[1][i][j] = max(t[1][i - 1][j], t[1][i - 1][min(n, j + curlen)]);
                  }
            }
      }

      for(int i = 0; i < q; i ++){
            int l1, l2, r1, r2;
            l1 = pos[S[i]], r1 = pos[S[i]];
            l2 = pos[E[i]], r2 = pos[E[i]];
            int lo = 1, hi = l1, ret = l1;
            while(lo <= hi){
                  int md = (lo + hi) >> 1;
                  if(get(md, l1, 0) >= L[i])
                        hi = md - 1, ret = md;
                  else
                        lo = md + 1;
            }
            l1 = ret;
            lo = r1, hi = n;
            while(lo <= hi){
                  int md = (lo + hi) >> 1;
                  if(get(r1, md, 0) >= L[i])
                        lo = md + 1, ret = md;
                  else
                        hi = md - 1;
            }
            r1 = ret;
            lo = 1, hi = l2, ret = l2;
            while(lo <= hi){
                  int md = (lo + hi) >> 1;
                  if(get(md, l2, 1) <= R[i])
                        hi = md - 1, ret = md;
                  else
                        lo = md + 1;
            }
            l2 = ret;
            lo = r2, hi = n;
            while(lo <= hi){
                  int md = (lo + hi) >> 1;
                  if(get(r2, md, 1) <= R[i])
                        lo = md + 1, ret = md;
                  else
                        hi = md - 1;
            }
            r2 = ret;
            if(max(l1, l2) <= min(r1, r2))
                  A[i] = 1;
      }

      return A;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 64 ms 58872 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 64 ms 58872 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 852 ms 66604 KB Output is correct
2 Correct 721 ms 68856 KB Output is correct
3 Correct 673 ms 68840 KB Output is correct
4 Correct 731 ms 68944 KB Output is correct
5 Correct 756 ms 68856 KB Output is correct
6 Correct 798 ms 68704 KB Output is correct
7 Correct 775 ms 68856 KB Output is correct
8 Correct 601 ms 68728 KB Output is correct
9 Correct 429 ms 68856 KB Output is correct
10 Correct 465 ms 68856 KB Output is correct
11 Correct 531 ms 68984 KB Output is correct
12 Correct 477 ms 68856 KB Output is correct
13 Correct 790 ms 69004 KB Output is correct
14 Correct 759 ms 68856 KB Output is correct
15 Correct 679 ms 68984 KB Output is correct
16 Correct 741 ms 68856 KB Output is correct
17 Correct 780 ms 68728 KB Output is correct

Subtask #4
0 / 51.0

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