oj.uz

답안 #972141

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
972141 2024-04-30T07:19:27 Z duckindog 늑대인간 (IOI18_werewolf) C++17
100 / 100
 883 ms 165712 KB 
#include <bits/stdc++.h>

#ifndef LOCAL
#include "werewolf.h"
#endif

using namespace std;

const int N = 200'000 + 10;
int n, m, q;
vector<int> ad[N];
 
struct Edge { 
  int u, v;
} edge[N << 1];

struct couldCan { 
  vector<int> ad[N << 1];
  int f[N << 1][19];
  int st[N << 1], ed[N << 1], rvs[N << 1], it;
  int w[N << 1];

  int id[N << 1];

  couldCan() { memset(id, -1, sizeof id); }

  int root(int u) { return id[u] < 0 ? u : id[u] = root(id[u]); }
  void add(int u, int v) {
    u = root(u); v = root(v);
    if (u == v) return;
    if (u < v) swap(u, v);
    id[v] = u;
  }

  void dfs(int u, int p = -1) { 
    for (int i = 1; i <= 18; ++i) f[u][i] = f[f[u][i - 1]][i - 1];
    
    st[u] = ++it; rvs[it] = u;
    
    for (const auto& v : ad[u]) { 
      f[v][0] = u;
      dfs(v, u);
    }

    ed[u] = it;
  }

} T[2];

struct Query {
  int cst, v, idx;
};
vector<Query> Q[N << 1];

struct BIT { 
  int n;
  int bit[N << 1], g[N << 1], idx;
  void clear() { idx += 1; }
  int& val(int i) { 
    if (g[i] != idx) {
      bit[i] = 0;
      g[i] = idx;
    }
    return bit[i];
  }
  void upd(int i, int x) {
    for (; i <= n; i += i & -i) val(i) += x;
  }
  int que(int i) { 
    int ret = 0;
    for (; i; i -= i & -i) ret += val(i);
    return ret;
  }
} f;

vector<int> check_validity(int n_, vector<int> x, vector<int> y,
                                vector<int> s, vector<int> e,
                                vector<int> l, vector<int> r) {
  n = n_; m = x.size(); q = s.size();

  for (int i = 0; i < m; ++i) { 
    int u = x[i], v = y[i];
    ad[u].push_back(v);
    ad[v].push_back(u);
    edge[i] = {u, v};
  }

  for (int t = 0; t < 2; ++t) { 
    auto& tree = T[t];

    auto weight = [&](const auto& edge) { 
      if (!t) return min(edge.u, edge.v);
      return max(edge.u, edge.v);
    };
    sort(edge, edge + m, [&](const auto& a, const auto& b) { 
      if (!t) return weight(a) > weight(b);
      return weight(a) < weight(b);
    });

    int it = n - 1;
    for (int i = 0; i < m; ++i) { 
      auto [u, v] = edge[i];
      int w = weight(edge[i]);

      if (tree.root(u) == tree.root(v)) continue;

      it += 1;
      
      tree.add(it, u = tree.root(u)); tree.add(it, v = tree.root(v));
      tree.ad[it].push_back(u);
      tree.ad[it].push_back(v);
      
      tree.w[it] = w;
    }
    tree.dfs(tree.f[it][0] = it);
  }

  for (int i = 0; i < q; ++i) { 
    { //human
      const auto& tree = T[0];
      for (int j = 18; j >= 0; --j) if (tree.w[tree.f[s[i]][j]] >= l[i]) s[i] = tree.f[s[i]][j];
    }
    { //wolf
      const auto& tree = T[1];
      for (int j = 18; j >= 0; --j) if (tree.w[tree.f[e[i]][j]] <= r[i]) e[i] = tree.f[e[i]][j];
    }
    Q[T[0].st[s[i]] - 1].push_back({-1, e[i], i});
    Q[T[0].ed[s[i]]].push_back({1, e[i], i});
  }
  f.n = T[1].it;

  vector<int> answer(q);
  for (int i = 1; i <= T[0].it; ++i) { 
    const auto& id = T[0].rvs[i];
    if (id < n) f.upd(T[1].st[id], 1);
    for (const auto& [cst, v, idx] : Q[i]) { 
      answer[idx] += cst * (f.que(T[1].ed[v]) - f.que(T[1].st[v] - 1));
    }
  }
  for (int i = 0; i < q; ++i) answer[i] = (answer[i] > 0);

  return answer;
}

#ifdef LOCAL
int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  int n_, m_, q_; cin >> n_ >> m_ >> q_;
  vector<int> x_(m_), y_(m_), s_(q_), e_(q_), l_(q_), r_(q_);
  for (int j = 0; j < m_; ++j) cin >> x_[j] >> y_[j];

  for (int i = 0; i < q_; ++i) cin >> s_[i] >> e_[i] >> l_[i] >> r_[i];

  for (const auto& x : check_validity(n_, x_, y_, s_, e_, l_, r_)) cerr << x << "\n";
}
#endif

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 46684 KB Output is correct
2 Correct 10 ms 46912 KB Output is correct
3 Correct 11 ms 46904 KB Output is correct
4 Correct 10 ms 46680 KB Output is correct
5 Correct 10 ms 44632 KB Output is correct
6 Correct 11 ms 44856 KB Output is correct
7 Correct 10 ms 42588 KB Output is correct
8 Correct 9 ms 42584 KB Output is correct
9 Correct 10 ms 42588 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 46684 KB Output is correct
2 Correct 10 ms 46912 KB Output is correct
3 Correct 11 ms 46904 KB Output is correct
4 Correct 10 ms 46680 KB Output is correct
5 Correct 10 ms 44632 KB Output is correct
6 Correct 11 ms 44856 KB Output is correct
7 Correct 10 ms 42588 KB Output is correct
8 Correct 9 ms 42584 KB Output is correct
9 Correct 10 ms 42588 KB Output is correct
10 Correct 15 ms 43608 KB Output is correct
11 Correct 18 ms 43612 KB Output is correct
12 Correct 15 ms 43608 KB Output is correct
13 Correct 15 ms 41652 KB Output is correct
14 Correct 15 ms 43676 KB Output is correct
15 Correct 16 ms 41940 KB Output is correct

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 751 ms 155248 KB Output is correct
2 Correct 650 ms 157288 KB Output is correct
3 Correct 560 ms 155268 KB Output is correct
4 Correct 570 ms 153548 KB Output is correct
5 Correct 551 ms 153708 KB Output is correct
6 Correct 630 ms 154884 KB Output is correct
7 Correct 634 ms 153420 KB Output is correct
8 Correct 591 ms 157436 KB Output is correct
9 Correct 489 ms 154116 KB Output is correct
10 Correct 488 ms 153396 KB Output is correct
11 Correct 456 ms 153336 KB Output is correct
12 Correct 555 ms 154888 KB Output is correct
13 Correct 824 ms 160524 KB Output is correct
14 Correct 790 ms 159948 KB Output is correct
15 Correct 840 ms 159524 KB Output is correct
16 Correct 794 ms 159572 KB Output is correct
17 Correct 654 ms 154524 KB Output is correct

Subtask #4
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 46684 KB Output is correct
2 Correct 10 ms 46912 KB Output is correct
3 Correct 11 ms 46904 KB Output is correct
4 Correct 10 ms 46680 KB Output is correct
5 Correct 10 ms 44632 KB Output is correct
6 Correct 11 ms 44856 KB Output is correct
7 Correct 10 ms 42588 KB Output is correct
8 Correct 9 ms 42584 KB Output is correct
9 Correct 10 ms 42588 KB Output is correct
10 Correct 15 ms 43608 KB Output is correct
11 Correct 18 ms 43612 KB Output is correct
12 Correct 15 ms 43608 KB Output is correct
13 Correct 15 ms 41652 KB Output is correct
14 Correct 15 ms 43676 KB Output is correct
15 Correct 16 ms 41940 KB Output is correct
16 Correct 751 ms 155248 KB Output is correct
17 Correct 650 ms 157288 KB Output is correct
18 Correct 560 ms 155268 KB Output is correct
19 Correct 570 ms 153548 KB Output is correct
20 Correct 551 ms 153708 KB Output is correct
21 Correct 630 ms 154884 KB Output is correct
22 Correct 634 ms 153420 KB Output is correct
23 Correct 591 ms 157436 KB Output is correct
24 Correct 489 ms 154116 KB Output is correct
25 Correct 488 ms 153396 KB Output is correct
26 Correct 456 ms 153336 KB Output is correct
27 Correct 555 ms 154888 KB Output is correct
28 Correct 824 ms 160524 KB Output is correct
29 Correct 790 ms 159948 KB Output is correct
30 Correct 840 ms 159524 KB Output is correct
31 Correct 794 ms 159572 KB Output is correct
32 Correct 654 ms 154524 KB Output is correct
33 Correct 842 ms 157536 KB Output is correct
34 Correct 283 ms 79856 KB Output is correct
35 Correct 834 ms 160080 KB Output is correct
36 Correct 758 ms 157008 KB Output is correct
37 Correct 871 ms 159232 KB Output is correct
38 Correct 806 ms 157652 KB Output is correct
39 Correct 792 ms 162980 KB Output is correct
40 Correct 824 ms 162896 KB Output is correct
41 Correct 673 ms 156500 KB Output is correct
42 Correct 571 ms 153808 KB Output is correct
43 Correct 774 ms 161876 KB Output is correct
44 Correct 689 ms 157496 KB Output is correct
45 Correct 582 ms 160192 KB Output is correct
46 Correct 588 ms 160296 KB Output is correct
47 Correct 813 ms 158716 KB Output is correct
48 Correct 867 ms 158472 KB Output is correct
49 Correct 801 ms 158540 KB Output is correct
50 Correct 883 ms 158156 KB Output is correct
51 Correct 749 ms 163192 KB Output is correct
52 Correct 832 ms 165712 KB Output is correct