oj.uz

Submission #837364

# Submission time Handle Problem Language Result Execution time Memory
837364 2023-08-25T09:57:00 Z becaido Werewolf (IOI18_werewolf) C++17
100 / 100
 624 ms 123748 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

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

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() { cout << "\n"; }
template<typename T, typename...U>
void dout(T t, U...u) { cout << t << (sizeof...(u) ? ", " : ""), dout(u...); }
#else
#define debug(...) 7122s
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for(int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 2e5 + 5;
const int H = __lg(SIZE);

int n, m, q;
vector<int> ans, adj[SIZE], ask[SIZE];

struct DSU {
    int to[SIZE];
    DSU() = default;
    void init() {
        iota(to, to + n, 0);
    }
    int dsu(int x) {
        return x == to[x] ? x : (to[x] = dsu(to[x]));
    }
};

struct Tree {
    vector<int> adj[SIZE];
    int root, to[SIZE][H + 1], h[SIZE];
    int dfsid, in[SIZE], out[SIZE], w[SIZE];
    DSU dsu;
    Tree() = default;
    void init() {
        dfsid = -1;
        dsu.init();
    }
    void add(int a, int b) {
        a = dsu.dsu(a), b = dsu.dsu(b);
        if (a == b) return;
        adj[a].pb(b);
        dsu.to[b] = a;
        root = a;
    }
    void build() {
        auto dfs = [&](auto dfs, int pos)->void {
            in[pos] = ++dfsid;
            w[pos] = 1;
            for (int np : adj[pos]) {
                h[np] = h[pos] + 1;
                to[np][0] = pos;
                dfs(dfs, np);
                w[pos] += w[np];
            }
            out[pos] = dfsid;
        };
        to[root][0] = root;
        dfs(dfs, root);
        FOR (j, 1, H) FOR (i, 0, n - 1) to[i][j] = to[to[i][j - 1]][j - 1];
    }
    int sch(int pos, int lim, int ty) {
        for (int i = H; i >= 0; i--) if ((ty == 1 && to[pos][i] >= lim) || (ty == 2 && to[pos][i] <= lim)) pos = to[pos][i];
        return pos;
    }
} t1, t2;

int bit[SIZE];
void upd(int pos, int x) {
    for (pos++; pos <= n; pos += pos & -pos) bit[pos] += x;
}
int que(int pos) {
    int re = 0;
    for (pos++; pos; pos -= pos & -pos) re += bit[pos];
    return re;
}
int que(int l, int r) {
    return que(r) - que(l - 1);
}

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();
    ans.resize(q);
    FOR (i, 0, m - 1) {
        adj[X[i]].pb(Y[i]);
        adj[Y[i]].pb(X[i]);
    }
    t1.init(), t2.init();
    for (int i = n - 1; i >= 0; i--) for (int j : adj[i]) if (i < j) t1.add(i, j);
    FOR (i, 0, n - 1) for (int j : adj[i]) if (i > j) t2.add(i, j);
    t1.build(), t2.build();
    FOR (i, 0, q - 1) {
        S[i] = t1.sch(S[i], L[i], 1);
        E[i] = t2.sch(E[i], R[i], 2);
        ask[S[i]].pb(i);
    }
    auto add = [&](auto add, int pos, int coef)->void {
        upd(t2.in[pos], coef);
        for (int np : t1.adj[pos]) add(add, np, coef);
    };
    auto dfs = [&](auto dfs, int pos)->void {
        int son = -1;
        for (int np : t1.adj[pos]) if (son == -1 || t1.w[np] > t1.w[son]) son = np;
        for (int np : t1.adj[pos]) if (np != son) {
            dfs(dfs, np);
            add(add, np, -1);
        }
        if (son != -1) dfs(dfs, son);
        for (int np : t1.adj[pos]) if (np != son) add(add, np, 1);
        upd(t2.in[pos], 1);
        for (int i : ask[pos]) {
            int l = t2.in[E[i]], r = t2.out[E[i]];
            ans[i] = que(l, r) > 0;
        }
    };
    dfs(dfs, 0);
    return ans;
}

/*
in1
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
out1
1
0
0
*/

#ifdef WAIMAI
namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

int main() {
  int N = read_int();
  int M = read_int();
  int Q = read_int();
  vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
  for (int j = 0; j < M; ++j) {
    X[j] = read_int();
    Y[j] = read_int();
  }
  for (int i = 0; i < Q; ++i) {
    S[i] = read_int();
    E[i] = read_int();
    L[i] = read_int();
    R[i] = read_int();
  }

  vector<int> A = check_validity(N, X, Y, S, E, L, R);
  for (size_t i = 0; i < A.size(); ++i) {
    printf("%d\n", A[i]);
  }
  return 0;
}
#endif

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19156 KB Output is correct
2 Correct 11 ms 19108 KB Output is correct
3 Correct 10 ms 19156 KB Output is correct
4 Correct 12 ms 19156 KB Output is correct
5 Correct 10 ms 19184 KB Output is correct
6 Correct 11 ms 19156 KB Output is correct
7 Correct 11 ms 19156 KB Output is correct
8 Correct 11 ms 19116 KB Output is correct
9 Correct 11 ms 19156 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19156 KB Output is correct
2 Correct 11 ms 19108 KB Output is correct
3 Correct 10 ms 19156 KB Output is correct
4 Correct 12 ms 19156 KB Output is correct
5 Correct 10 ms 19184 KB Output is correct
6 Correct 11 ms 19156 KB Output is correct
7 Correct 11 ms 19156 KB Output is correct
8 Correct 11 ms 19116 KB Output is correct
9 Correct 11 ms 19156 KB Output is correct
10 Correct 15 ms 20436 KB Output is correct
11 Correct 14 ms 20332 KB Output is correct
12 Correct 15 ms 20180 KB Output is correct
13 Correct 14 ms 20308 KB Output is correct
14 Correct 18 ms 20400 KB Output is correct
15 Correct 19 ms 20608 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 92864 KB Output is correct
2 Correct 386 ms 96632 KB Output is correct
3 Correct 359 ms 92040 KB Output is correct
4 Correct 420 ms 91548 KB Output is correct
5 Correct 422 ms 91644 KB Output is correct
6 Correct 507 ms 92320 KB Output is correct
7 Correct 553 ms 91720 KB Output is correct
8 Correct 390 ms 96640 KB Output is correct
9 Correct 326 ms 91856 KB Output is correct
10 Correct 361 ms 91176 KB Output is correct
11 Correct 351 ms 91164 KB Output is correct
12 Correct 438 ms 91012 KB Output is correct
13 Correct 624 ms 123624 KB Output is correct
14 Correct 506 ms 123528 KB Output is correct
15 Correct 527 ms 123584 KB Output is correct
16 Correct 530 ms 123660 KB Output is correct
17 Correct 481 ms 91724 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19156 KB Output is correct
2 Correct 11 ms 19108 KB Output is correct
3 Correct 10 ms 19156 KB Output is correct
4 Correct 12 ms 19156 KB Output is correct
5 Correct 10 ms 19184 KB Output is correct
6 Correct 11 ms 19156 KB Output is correct
7 Correct 11 ms 19156 KB Output is correct
8 Correct 11 ms 19116 KB Output is correct
9 Correct 11 ms 19156 KB Output is correct
10 Correct 15 ms 20436 KB Output is correct
11 Correct 14 ms 20332 KB Output is correct
12 Correct 15 ms 20180 KB Output is correct
13 Correct 14 ms 20308 KB Output is correct
14 Correct 18 ms 20400 KB Output is correct
15 Correct 19 ms 20608 KB Output is correct
16 Correct 560 ms 92864 KB Output is correct
17 Correct 386 ms 96632 KB Output is correct
18 Correct 359 ms 92040 KB Output is correct
19 Correct 420 ms 91548 KB Output is correct
20 Correct 422 ms 91644 KB Output is correct
21 Correct 507 ms 92320 KB Output is correct
22 Correct 553 ms 91720 KB Output is correct
23 Correct 390 ms 96640 KB Output is correct
24 Correct 326 ms 91856 KB Output is correct
25 Correct 361 ms 91176 KB Output is correct
26 Correct 351 ms 91164 KB Output is correct
27 Correct 438 ms 91012 KB Output is correct
28 Correct 624 ms 123624 KB Output is correct
29 Correct 506 ms 123528 KB Output is correct
30 Correct 527 ms 123584 KB Output is correct
31 Correct 530 ms 123660 KB Output is correct
32 Correct 481 ms 91724 KB Output is correct
33 Correct 481 ms 96720 KB Output is correct
34 Correct 193 ms 52488 KB Output is correct
35 Correct 484 ms 108828 KB Output is correct
36 Correct 508 ms 95920 KB Output is correct
37 Correct 514 ms 105756 KB Output is correct
38 Correct 566 ms 98508 KB Output is correct
39 Correct 620 ms 102132 KB Output is correct
40 Correct 585 ms 111980 KB Output is correct
41 Correct 394 ms 102056 KB Output is correct
42 Correct 398 ms 94056 KB Output is correct
43 Correct 561 ms 120456 KB Output is correct
44 Correct 605 ms 104544 KB Output is correct
45 Correct 502 ms 100420 KB Output is correct
46 Correct 404 ms 100208 KB Output is correct
47 Correct 541 ms 123748 KB Output is correct
48 Correct 570 ms 123636 KB Output is correct
49 Correct 547 ms 123724 KB Output is correct
50 Correct 517 ms 123692 KB Output is correct
51 Correct 540 ms 111644 KB Output is correct
52 Correct 556 ms 111652 KB Output is correct