oj.uz

Submission #1066134

# Submission time Handle Problem Language Result Execution time Memory
1066134 2024-08-19T15:18:06 Z blackslex Werewolf (IOI18_werewolf) C++17
0 / 100
 306 ms 68624 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++) {
    if (ival[i].second >= ival2[i].first) 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 18 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 18 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 306 ms 68624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

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