oj.uz

Submission #1066191

# Submission time Handle Problem Language Result Execution time Memory
1066191 2024-08-19T16:12:36 Z blackslex Werewolf (IOI18_werewolf) C++17
34 / 100
 274 ms 68496 KB 
#include "werewolf.h"
#include<bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
  int n = N, m = X.size(), q = S.size();
  vector<vector<int>> v(n, vector<int>());
  vector<int> a(n), par(n), mx(n), mn(n);
  iota(par.begin(), par.end(), 0);
  for (int i = 0; i < m; i++) v[X[i]].emplace_back(Y[i]), v[Y[i]].emplace_back(X[i]);
  int st = -1, curidx = -1;
  for (int i = 0; i < n; i++) if (v[i].size() == 1) st = i;
  function<void(int, int)> dfs = [&] (int cur, int par) {
    a[++curidx] = cur;
    for (auto &e: v[cur]) {
      if (par == e) continue;
      dfs(e, cur);
    }
  };
  dfs(st, -1);
  for (int i = 0; i < n; i++) mx[a[i]] = mn[a[i]] = i;
  function<int(int)> fset = [&] (int x) {return (par[x] == x ? x : par[x] = fset(par[x]));};
  auto mg = [&] (int x, int y) {
    if ((x = fset(x)) == (y = fset(y))) return;
    mx[x] = max(mx[x], mx[y]);
    mn[x] = min(mn[x], mn[y]);
    par[y] = x;
  };
  vector<vector<pii>> ev(n), ev2(n);
  vector<pii> ival(q), ival2(q);
  for (int i = 0; i < q; i++) {
    int cs = S[i], ce = E[i], cl = L[i], cr = R[i];
    ev[L[i]].emplace_back(cs, i);
    ev2[R[i]].emplace_back(ce, i);
  }
  vector<int> ans(q);
  for (int i = n - 1; i >= 0; i--) {
    for (auto &e: v[i]) if (e >= i) mg(i, e);
    for (auto &[x, y]: ev[i]) ival[y] = pii(mn[fset(x)], mx[fset(x)]);
  }
  iota(par.begin(), par.end(), 0);
  for (int i = 0; i < n; i++) mx[a[i]] = mn[a[i]] = i;
  for (int i = 0; i < n; i++) {
    for (auto &e: v[i]) if (e <= i) mg(i, e);
    for (auto &[x, y]: ev2[i]) ival2[y] = pii(mn[fset(x)], mx[fset(x)]);
  }
  for (int i = 0; i < q; i++) {
    auto ck = [&] (int x, int y, int z) {
      return z >= x && z <= y;
    };
    if (ck(ival[i].first, ival[i].second, ival2[i].first)) ans[i] = 1;
    if (ck(ival[i].first, ival[i].second, ival2[i].second)) ans[i] = 1;
    if (ck(ival2[i].first, ival2[i].second, ival[i].first)) ans[i] = 1;
    if (ck(ival2[i].first, ival2[i].second, ival[i].second)) ans[i] = 1;
  }
  return ans;
}

Compilation message

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:36:31: warning: unused variable 'cl' [-Wunused-variable]
   36 |     int cs = S[i], ce = E[i], cl = L[i], cr = R[i];
      |                               ^~
werewolf.cpp:36:42: warning: unused variable 'cr' [-Wunused-variable]
   36 |     int cs = S[i], ce = E[i], cl = L[i], cr = R[i];
      |                                          ^~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 68420 KB Output is correct
2 Correct 274 ms 68480 KB Output is correct
3 Correct 247 ms 68440 KB Output is correct
4 Correct 239 ms 68432 KB Output is correct
5 Correct 259 ms 68436 KB Output is correct
6 Correct 231 ms 68488 KB Output is correct
7 Correct 210 ms 66596 KB Output is correct
8 Correct 216 ms 68432 KB Output is correct
9 Correct 197 ms 67328 KB Output is correct
10 Correct 196 ms 67156 KB Output is correct
11 Correct 203 ms 67596 KB Output is correct
12 Correct 216 ms 68432 KB Output is correct
13 Correct 233 ms 68492 KB Output is correct
14 Correct 256 ms 68496 KB Output is correct
15 Correct 242 ms 68488 KB Output is correct
16 Correct 255 ms 68496 KB Output is correct
17 Correct 218 ms 66512 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -