oj.uz

Submission #123207

# Submission time Handle Problem Language Result Execution time Memory
123207 2019-06-30T11:37:12 Z nvmdava Werewolf (IOI18_werewolf) C++17
100 / 100
 1387 ms 184172 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;

int p[2][200005][20];
int tp[2][200005];
int d[2][200005][20];
vector<int> adj[200005];
vector<int> child[2][200005];
int n ;
int find(int i, int id){
   if(i == tp[id][i]){
      return i;
   }
   return tp[id][i] = find(tp[id][i], id);
}
void build(int i, int id){
   for(int x : adj[i]){
      if((id == 0) ^ (x > i) == 1){
         x = find(x, id);
         if(x == i) continue;
         p[id][x][0] = i;
         tp[id][x] = i;
      }
   }
}
int cnt = 0;
int l[2][200005], r[2][200005];
int arr[2][200005];
int inv[200005];
void dfs(int v, int id){
   if((id == 1 && v == 0) || (id == 0 && v == n - 1)){

   } else {
      d[id][v][0] = id == 0 ? max(v, p[id][v][0]) : min(v, p[id][v][0]);
      for(int j = 1; j < 20; j++){
         if(p[id][v][j - 1] == -1) break;
         p[id][v][j] = p[id][p[id][v][j - 1]][j - 1];
         d[id][v][j] = id == 0 ? max(d[id][v][j - 1], d[id][p[id][v][j - 1]][j - 1]) : min(d[id][v][j - 1], d[id][p[id][v][j - 1]][j - 1]);
      }
   }
   l[id][v] = ++cnt;
   arr[id][cnt] = v;
   for(int x :child[id][v]){
      dfs(x, id);
   }
   r[id][v] = cnt;
}

vector<int> seg[530000];
void builder(int id, int l, int r){
   if(l == r){
      seg[id].push_back(arr[0][l]);
      return;
   }
   int m = (l + r) >> 1, id1 = id << 1, id2 = id << 1 | 1, it1 = 0, it2;
   builder(id1, l, m);
   builder(id2, m + 1, r);
   int sz1 = seg[id1].size();
   int sz2 = seg[id2].size();
   while(it1 != sz1 && it2 != sz2){
      if(seg[id1][it1] > seg[id2][it2])
         seg[id].push_back(seg[id2][it2++]);
      else
         seg[id].push_back(seg[id1][it1++]);
   }
   while(it1 != sz1)
         seg[id].push_back(seg[id1][it1++]);
   while(it2 != sz2)
         seg[id].push_back(seg[id2][it2++]);
}

bool query(int id, int l, int r, int L, int R, int D, int U){
   if(r < L || l > R) return 0;
   if(l >= L && r <= R){
      return 0 != upper_bound(seg[id].begin(), seg[id].end(), U) - lower_bound(seg[id].begin(), seg[id].end(), D);
   }
   int m = (l + r) >> 1;
   if(query(id << 1, l, m, L, R, D, U)) return 1;
   if(query(id << 1 | 1, m + 1, r, L, R, D, U)) return 1;
   return 0;
}


bool answer(int s, int e, int L, int R){
   for(int i = 19; i >= 0; i--){
      if(p[1][s][i] != -1 && d[1][s][i] >= L)
         s = p[1][s][i];
      if(p[0][e][i] != -1 && d[0][e][i] <= R)
         e = p[0][e][i];
   }
   return query(1, 1, n, l[0][e], r[0][e], l[1][s], r[1][s]);
}


vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                              vector<int> L, vector<int> R) {
   memset(p, -1, sizeof p);
   for(int i = 0; i < N; i++){
      tp[0][i] = tp[1][i] = i;
   }
   n = N;
   for(int i = X.size() - 1; i >= 0; i--){
      adj[X[i]].push_back(Y[i]);
      adj[Y[i]].push_back(X[i]);
   }
   for(int i = 0; i < N; i++)
      build(i, 0);
   for(int i = N - 1; i >= 0; i--)
      build(i, 1);

   for(int i = 1; i < N; i++)
      child[1][p[1][i][0]].push_back(i);
   for(int i = N - 2; i >= 0; i--)
      child[0][p[0][i][0]].push_back(i);
   cnt = 0; dfs(0, 1);
   cnt = 0; dfs(N - 1, 0);
   for(int i = 1; i <= n; i++){
      inv[arr[1][i]] = i;
   }
   for(int i = 1; i <= n; i++){
      arr[0][i] = inv[arr[0][i]];
   }
   builder(1, 1, n);
   int Q = S.size();
   vector<int> A(Q);
   for (int i = 0; i < Q; ++i) {
      A[i] = answer(S[i], E[i], L[i], R[i]);
   }
   return A;
}

Compilation message

werewolf.cpp: In function 'void build(int, int)':
werewolf.cpp:19:30: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
       if((id == 0) ^ (x > i) == 1){
                      ~~~~~~~~^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 58360 KB Output is correct
2 Correct 51 ms 58232 KB Output is correct
3 Correct 52 ms 58232 KB Output is correct
4 Correct 52 ms 58232 KB Output is correct
5 Correct 52 ms 58236 KB Output is correct
6 Correct 52 ms 58232 KB Output is correct
7 Correct 57 ms 58296 KB Output is correct
8 Correct 52 ms 58232 KB Output is correct
9 Correct 61 ms 58232 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 58360 KB Output is correct
2 Correct 51 ms 58232 KB Output is correct
3 Correct 52 ms 58232 KB Output is correct
4 Correct 52 ms 58232 KB Output is correct
5 Correct 52 ms 58236 KB Output is correct
6 Correct 52 ms 58232 KB Output is correct
7 Correct 57 ms 58296 KB Output is correct
8 Correct 52 ms 58232 KB Output is correct
9 Correct 61 ms 58232 KB Output is correct
10 Correct 68 ms 59788 KB Output is correct
11 Correct 71 ms 59768 KB Output is correct
12 Correct 70 ms 59768 KB Output is correct
13 Correct 61 ms 59896 KB Output is correct
14 Correct 61 ms 59896 KB Output is correct
15 Correct 62 ms 59860 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1049 ms 164576 KB Output is correct
2 Correct 957 ms 168300 KB Output is correct
3 Correct 927 ms 174308 KB Output is correct
4 Correct 982 ms 173336 KB Output is correct
5 Correct 1086 ms 173244 KB Output is correct
6 Correct 1148 ms 173200 KB Output is correct
7 Correct 1072 ms 173032 KB Output is correct
8 Correct 935 ms 176624 KB Output is correct
9 Correct 909 ms 174444 KB Output is correct
10 Correct 780 ms 173196 KB Output is correct
11 Correct 940 ms 173292 KB Output is correct
12 Correct 1051 ms 173196 KB Output is correct
13 Correct 1201 ms 182008 KB Output is correct
14 Correct 1221 ms 181948 KB Output is correct
15 Correct 1224 ms 182028 KB Output is correct
16 Correct 1179 ms 181996 KB Output is correct
17 Correct 1064 ms 173292 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 58360 KB Output is correct
2 Correct 51 ms 58232 KB Output is correct
3 Correct 52 ms 58232 KB Output is correct
4 Correct 52 ms 58232 KB Output is correct
5 Correct 52 ms 58236 KB Output is correct
6 Correct 52 ms 58232 KB Output is correct
7 Correct 57 ms 58296 KB Output is correct
8 Correct 52 ms 58232 KB Output is correct
9 Correct 61 ms 58232 KB Output is correct
10 Correct 68 ms 59788 KB Output is correct
11 Correct 71 ms 59768 KB Output is correct
12 Correct 70 ms 59768 KB Output is correct
13 Correct 61 ms 59896 KB Output is correct
14 Correct 61 ms 59896 KB Output is correct
15 Correct 62 ms 59860 KB Output is correct
16 Correct 1049 ms 164576 KB Output is correct
17 Correct 957 ms 168300 KB Output is correct
18 Correct 927 ms 174308 KB Output is correct
19 Correct 982 ms 173336 KB Output is correct
20 Correct 1086 ms 173244 KB Output is correct
21 Correct 1148 ms 173200 KB Output is correct
22 Correct 1072 ms 173032 KB Output is correct
23 Correct 935 ms 176624 KB Output is correct
24 Correct 909 ms 174444 KB Output is correct
25 Correct 780 ms 173196 KB Output is correct
26 Correct 940 ms 173292 KB Output is correct
27 Correct 1051 ms 173196 KB Output is correct
28 Correct 1201 ms 182008 KB Output is correct
29 Correct 1221 ms 181948 KB Output is correct
30 Correct 1224 ms 182028 KB Output is correct
31 Correct 1179 ms 181996 KB Output is correct
32 Correct 1064 ms 173292 KB Output is correct
33 Correct 1253 ms 173568 KB Output is correct
34 Correct 407 ms 89720 KB Output is correct
35 Correct 1277 ms 176308 KB Output is correct
36 Correct 1192 ms 173792 KB Output is correct
37 Correct 1367 ms 175516 KB Output is correct
38 Correct 1273 ms 174316 KB Output is correct
39 Correct 1387 ms 183916 KB Output is correct
40 Correct 1365 ms 183988 KB Output is correct
41 Correct 1215 ms 174828 KB Output is correct
42 Correct 872 ms 173736 KB Output is correct
43 Correct 1223 ms 181452 KB Output is correct
44 Correct 1215 ms 175468 KB Output is correct
45 Correct 1142 ms 184172 KB Output is correct
46 Correct 1101 ms 184016 KB Output is correct
47 Correct 1341 ms 182172 KB Output is correct
48 Correct 1198 ms 182020 KB Output is correct
49 Correct 1208 ms 182076 KB Output is correct
50 Correct 1177 ms 181968 KB Output is correct
51 Correct 1323 ms 183916 KB Output is correct
52 Correct 1361 ms 183788 KB Output is correct