oj.uz

Submission #1044918

# Submission time Handle Problem Language Result Execution time Memory
1044918 2024-08-05T14:34:24 Z VMaksimoski008 Werewolf (IOI18_werewolf) C++17
100 / 100
 559 ms 226852 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 6e5 + 5;

struct BIT {
    int n;
    vector<int> tree;

    void config(int _n) {
        n = _n + 10;
        tree.resize(_n+60);
    }

    void update(int p, int v) {
        for(p++; p<n; p+=p&-p) tree[p] += v;
    }

    int query(int p) {
        int ans = 0;
        for(p++; p>0; p-=p&-p) ans += tree[p];
        return ans;
    }

    int query(int l, int r) { return query(r) - query(l-1); }
};

int par[2][maxn], n, d[2][maxn], mn[maxn], mx[maxn], out[2][maxn], up[2][maxn][21], in[2][maxn], timer[2];
vector<int> graph[2][maxn], euler[2];
vector<int> by_x[maxn+5];

int find(int u, int t) {
    if(par[t][u] == u) return u;
    return par[t][u] = find(par[t][u], t);
}

void uni(int a, int b, int t) {
    a = find(a, t); b = find(b, t);
    if(a == b) return ;
    n++;
    par[t][n] = par[t][a] = par[t][b] = n;
    graph[t][n].push_back(a);
    graph[t][n].push_back(b);
}

void dfs(int u, int t) {
    if(graph[t][u].empty()) {
        if(t == 0) mn[u] = u;
        else mx[u] = u;
    }

    in[t][u] = timer[t]++; euler[t].push_back(u);
    for(int i=1; i<21; i++) up[t][u][i] = up[t][up[t][u][i-1]][i-1];

    for(int &v : graph[t][u]) {
        d[t][v] = d[t][u] + 1;
        up[t][v][0] = u;
        dfs(v, t);
        if(t == 0) mn[u] = min(mn[u], mn[v]);
        else mx[u] = max(mx[u], mx[v]);
    }

    out[t][u] = timer[t] - 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) {
    int Q = S.size(), M = X.size();
    vector<int> ans(Q);

    for(int i=1; i<=N+M; i++) par[0][i] = par[1][i] = i, mn[i] = 1e9;

    vector<int> edges[N+1];
    for(int i=0; i<M; i++) {
        edges[X[i]+1].push_back(Y[i]+1);
        edges[Y[i]+1].push_back(X[i]+1);
    }

    n = N;
    for(int i=N; i>=1; i--)
        for(int &j : edges[i]) if(i < j) uni(i, j, 0);
    n = N;
    for(int i=1; i<=N; i++)
        for(int &j : edges[i]) if(i > j) uni(i, j, 1);

    dfs(n, 0); dfs(n, 1);

    vector<array<int, 4> > qus;    
    for(int i=1; i<=N; i++) by_x[in[0][i]].push_back(in[1][i]);
    for(int i=0; i<Q; i++) {
        S[i]++; E[i]++; L[i]++; R[i]++;
        if(S[i] < L[i] || E[i] > R[i]) continue;
        int p1 = S[i], p2 = E[i];

        for(int j=20; j>=0; j--) {
            if(up[0][p1][j] > 0 && mn[up[0][p1][j]] >= L[i]) p1 = up[0][p1][j];
            if(up[1][p2][j] > 0 && mx[up[1][p2][j]] <= R[i]) p2 = up[1][p2][j];
        }

        qus.push_back({ in[0][p1], out[0][p1], in[1][p2], out[1][p2] });
    }

    vector<int> on[n+1], off[n+1], add[n+1];
    for(int i=0; i<Q; i++) {
        on[qus[i][1]].push_back(i);
        if(qus[i][0]) off[qus[i][0]-1].push_back(i);
    }

    BIT bit; bit.config(n+1);
    for(int i=0; i<=n; i++) {
        for(int &p : by_x[i]) bit.update(p, 1);
        for(int &id : off[i]) ans[id] -= bit.query(qus[id][2], qus[id][3]);
        for(int &id : on[i]) ans[id] += bit.query(qus[id][2], qus[id][3]);
    }

    for(int i=0; i<Q; i++) {
        if(ans[i] >= 1) ans[i] = 1;
        else ans[i] = 0;
    }
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 57948 KB Output is correct
2 Correct 7 ms 58176 KB Output is correct
3 Correct 9 ms 57948 KB Output is correct
4 Correct 9 ms 58052 KB Output is correct
5 Correct 8 ms 57948 KB Output is correct
6 Correct 11 ms 58024 KB Output is correct
7 Correct 8 ms 58088 KB Output is correct
8 Correct 8 ms 58036 KB Output is correct
9 Correct 8 ms 57948 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 57948 KB Output is correct
2 Correct 7 ms 58176 KB Output is correct
3 Correct 9 ms 57948 KB Output is correct
4 Correct 9 ms 58052 KB Output is correct
5 Correct 8 ms 57948 KB Output is correct
6 Correct 11 ms 58024 KB Output is correct
7 Correct 8 ms 58088 KB Output is correct
8 Correct 8 ms 58036 KB Output is correct
9 Correct 8 ms 57948 KB Output is correct
10 Correct 11 ms 60252 KB Output is correct
11 Correct 14 ms 60348 KB Output is correct
12 Correct 12 ms 60392 KB Output is correct
13 Correct 13 ms 60380 KB Output is correct
14 Correct 13 ms 60252 KB Output is correct
15 Correct 12 ms 60508 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 217640 KB Output is correct
2 Correct 402 ms 219324 KB Output is correct
3 Correct 393 ms 219252 KB Output is correct
4 Correct 412 ms 219100 KB Output is correct
5 Correct 414 ms 219324 KB Output is correct
6 Correct 449 ms 221416 KB Output is correct
7 Correct 449 ms 219684 KB Output is correct
8 Correct 378 ms 220092 KB Output is correct
9 Correct 372 ms 218556 KB Output is correct
10 Correct 359 ms 219368 KB Output is correct
11 Correct 357 ms 218448 KB Output is correct
12 Correct 379 ms 219324 KB Output is correct
13 Correct 382 ms 220008 KB Output is correct
14 Correct 401 ms 220008 KB Output is correct
15 Correct 418 ms 220088 KB Output is correct
16 Correct 411 ms 220344 KB Output is correct
17 Correct 450 ms 220604 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 57948 KB Output is correct
2 Correct 7 ms 58176 KB Output is correct
3 Correct 9 ms 57948 KB Output is correct
4 Correct 9 ms 58052 KB Output is correct
5 Correct 8 ms 57948 KB Output is correct
6 Correct 11 ms 58024 KB Output is correct
7 Correct 8 ms 58088 KB Output is correct
8 Correct 8 ms 58036 KB Output is correct
9 Correct 8 ms 57948 KB Output is correct
10 Correct 11 ms 60252 KB Output is correct
11 Correct 14 ms 60348 KB Output is correct
12 Correct 12 ms 60392 KB Output is correct
13 Correct 13 ms 60380 KB Output is correct
14 Correct 13 ms 60252 KB Output is correct
15 Correct 12 ms 60508 KB Output is correct
16 Correct 556 ms 217640 KB Output is correct
17 Correct 402 ms 219324 KB Output is correct
18 Correct 393 ms 219252 KB Output is correct
19 Correct 412 ms 219100 KB Output is correct
20 Correct 414 ms 219324 KB Output is correct
21 Correct 449 ms 221416 KB Output is correct
22 Correct 449 ms 219684 KB Output is correct
23 Correct 378 ms 220092 KB Output is correct
24 Correct 372 ms 218556 KB Output is correct
25 Correct 359 ms 219368 KB Output is correct
26 Correct 357 ms 218448 KB Output is correct
27 Correct 379 ms 219324 KB Output is correct
28 Correct 382 ms 220008 KB Output is correct
29 Correct 401 ms 220008 KB Output is correct
30 Correct 418 ms 220088 KB Output is correct
31 Correct 411 ms 220344 KB Output is correct
32 Correct 450 ms 220604 KB Output is correct
33 Correct 506 ms 221560 KB Output is correct
34 Correct 160 ms 100260 KB Output is correct
35 Correct 559 ms 222228 KB Output is correct
36 Correct 495 ms 221560 KB Output is correct
37 Correct 503 ms 221880 KB Output is correct
38 Correct 492 ms 222140 KB Output is correct
39 Correct 533 ms 222136 KB Output is correct
40 Correct 510 ms 226852 KB Output is correct
41 Correct 450 ms 220092 KB Output is correct
42 Correct 416 ms 218864 KB Output is correct
43 Correct 488 ms 224184 KB Output is correct
44 Correct 475 ms 221116 KB Output is correct
45 Correct 426 ms 219480 KB Output is correct
46 Correct 417 ms 219332 KB Output is correct
47 Correct 435 ms 220344 KB Output is correct
48 Correct 393 ms 220600 KB Output is correct
49 Correct 402 ms 220348 KB Output is correct
50 Correct 404 ms 220864 KB Output is correct
51 Correct 489 ms 226492 KB Output is correct
52 Correct 537 ms 226456 KB Output is correct