oj.uz

Submission #1067064

# Submission time Handle Problem Language Result Execution time Memory
1067064 2024-08-20T10:33:01 Z TheQuantiX Werewolf (IOI18_werewolf) C++17
49 / 100
 795 ms 50516 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr ll INF = 100000000LL;

ll n, m, q, k, x, y, a, b, c;
vector<int> G[200000];
int to[200000];
int from[200000];

int bfs(ll s, ll e, ll l, ll r) {
    queue< pair<ll, bool> > q;
    q.push({s, 0});
    vector< vector<ll> > vis(n, vector<ll> (2, 0));
    vis[s][0] = 1;
    while (!q.empty()) {
        auto [x, w] = q.front();
        q.pop();
        // cout << x << ' ' << w << '\n';
        if (!vis[x][1] && x <= r) {
            q.push({x, 1});
            vis[x][1] = 1;
        }
        for (int i : G[x]) {
            if (!vis[i][w] && (w == 1 || i >= l) && (w == 0 || i <= r)) {
                q.push({i, w});
                vis[i][w] = 1;
            }
        }
    }
    // cout << '\n';
    return vis[e][1];
}

void dfs(ll x, ll p, ll num) {
    to[x] = num;
    from[num] = x;
    for (auto i : G[x]) {
        if (i != p) {
            dfs(i, x, num + 1);
        }
    }
}

struct segtree {
    ll n;
    vector<ll> mintr;
    vector<ll> maxtr;

    void build(ll x, ll l, ll r) {
        if (l == r) {
            mintr[x] = from[l];
            maxtr[x] = from[l];
            // cout << x << ' ' << mintr[x] << ' ' << maxtr[x] << '\n';
            return;
        }
        ll mid = (r + l) / 2;
        build(x * 2 + 1, l, mid);
        build(x * 2 + 2, mid + 1, r);
        mintr[x] = min(mintr[x * 2 + 1], mintr[x * 2 + 2]);
        maxtr[x] = max(maxtr[x * 2 + 1], maxtr[x * 2 + 2]);
        // cout << x << ' ' << mintr[x] << ' ' << maxtr[x] << '\n';
    }

    segtree(ll N) : n(N) {
        mintr.resize(4 * n);
        maxtr.resize(4 * n);
        build(0, 0, n - 1);
    }

    ll getmx(ll x, ll l, ll r, ll L, ll R) {
        if (r < l) {
            return -INF;
        }
        if (r < L) {
            return -INF;
        }
        if (R < l) {
            return -INF;
        }
        if (L <= l && r <= R) {
            // cout << x << ' ' << l << ' ' << r << ' ' << L << ' ' << R << '\n';
            // cout << maxtr[x] << '\n';
            return maxtr[x];
        }
        ll mid = (r + l) / 2;
        ll ans = max(getmx(x * 2 + 1, l, mid, L, R), getmx(x * 2 + 2, mid + 1, r, L, R));
        // cout << x << ' ' << l << ' ' << r << ' ' << L << ' ' << R << '\n';
        // cout << ans << '\n';
        return ans;
    }

    ll getmn(ll x, ll l, ll r, ll L, ll R) {
        if (r < l) {
            return INF;
        }
        if (r < L) {
            return INF;
        }
        if (R < l) {
            return INF;
        }
        if (L <= l && r <= R) {
            return mintr[x];
        }
        ll mid = (r + l) / 2;
        return min(getmn(x * 2 + 1, l, mid, L, R), getmn(x * 2 + 2, mid + 1, r, L, R));
    }
};

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++) {
        G[X[i]].push_back(Y[i]);
        G[Y[i]].push_back(X[i]);
    }
    vector<int> ans;
    if (n <= 3000 && m <= 6000 && q <= 3000) {
    // if (0) {
        for (int i = 0; i < q; i++) {
            ans.push_back(bfs(S[i], E[i], L[i], R[i]));
        }
    }
    else {
        ans.resize(q);
        ll x = 0;
        for (int i = 0; i < n; i++) {
            if (G[i].size() == 1) {
                x = i;
                break;
            }
        }
        dfs(x, -1, 0);
        // cout << (*from.rbegin()).first << endl;
        segtree sg(n);
        // cout << sg.getmx(0, 0, n - 1, 3, 6) << '\n';
        // exit(0);
        for (int i = 0; i < q; i++) {
            ll x = to[S[i]];
            ll y = to[E[i]];
            // cout << x << ' ' << y << '\n';
            if (x < y) {
                ll l = x, r = y + 1;
                while (r > l) {
                    ll mid = (r + l) / 2;
                    if (sg.getmn(0, 0, n - 1, x, mid) < L[i]) {
                        r = mid;
                    }
                    else {
                        l = mid + 1;
                    }
                }
                ans[i] = 1;
                if (l == x) {
                    ans[i] = 0;
                }
                if (from[l - 1] > R[i]) {
                    ans[i] = 0;
                }
                if (from[y] > R[i]) {
                    ans[i] = 0;
                }
                if (sg.getmx(0, 0, n - 1, l, y) > R[i]) {
                    ans[i] = 0;
                }
            }
            else {
                swap(x, y);
                // cout << x << ' ' << y << '\n';
                ll l = x, r = y + 1;
                while (r > l) {
                    // cout << l << ' ' << r << '\n';
                    ll mid = (r + l) / 2;
                    // cout << x << ' ' << mid << endl;
                    // cout << sg.getmx(0, 0, n - 1, x, mid) << ' ' << R[i] << '\n';
                    if (sg.getmx(0, 0, n - 1, x, mid) > R[i]) {
                        r = mid;
                    }
                    else {
                        l = mid + 1;
                    }
                    // cout << '\n';
                }
                // cout << l << '\n';
                // cout << "DEBUG" << endl;
                ans[i] = 1;
                if (l == x) {
                    ans[i] = 0;
                }
                if (from[l - 1] < L[i]) {
                    ans[i] = 0;
                }
                if (from[y] < L[i]) {
                    ans[i] = 0;
                }
                if (sg.getmn(0, 0, n - 1, l, y) < L[i]) {
                    ans[i] = 0;
                }
            }
        }
    }
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 2 ms 5124 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Correct 3 ms 4956 KB Output is correct
9 Correct 3 ms 4956 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 2 ms 5124 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Correct 3 ms 4956 KB Output is correct
9 Correct 3 ms 4956 KB Output is correct
10 Correct 626 ms 5668 KB Output is correct
11 Correct 539 ms 5716 KB Output is correct
12 Correct 299 ms 5468 KB Output is correct
13 Correct 585 ms 5672 KB Output is correct
14 Correct 481 ms 5468 KB Output is correct
15 Correct 617 ms 5724 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 740 ms 50256 KB Output is correct
2 Correct 795 ms 50260 KB Output is correct
3 Correct 743 ms 50260 KB Output is correct
4 Correct 768 ms 50348 KB Output is correct
5 Correct 790 ms 50344 KB Output is correct
6 Correct 761 ms 50260 KB Output is correct
7 Correct 765 ms 50344 KB Output is correct
8 Correct 778 ms 50272 KB Output is correct
9 Correct 342 ms 50260 KB Output is correct
10 Correct 416 ms 50256 KB Output is correct
11 Correct 533 ms 50516 KB Output is correct
12 Correct 503 ms 50256 KB Output is correct
13 Correct 748 ms 50260 KB Output is correct
14 Correct 786 ms 50144 KB Output is correct
15 Correct 769 ms 50512 KB Output is correct
16 Correct 788 ms 50348 KB Output is correct
17 Correct 764 ms 50148 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 2 ms 5124 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Correct 3 ms 4956 KB Output is correct
9 Correct 3 ms 4956 KB Output is correct
10 Correct 626 ms 5668 KB Output is correct
11 Correct 539 ms 5716 KB Output is correct
12 Correct 299 ms 5468 KB Output is correct
13 Correct 585 ms 5672 KB Output is correct
14 Correct 481 ms 5468 KB Output is correct
15 Correct 617 ms 5724 KB Output is correct
16 Correct 740 ms 50256 KB Output is correct
17 Correct 795 ms 50260 KB Output is correct
18 Correct 743 ms 50260 KB Output is correct
19 Correct 768 ms 50348 KB Output is correct
20 Correct 790 ms 50344 KB Output is correct
21 Correct 761 ms 50260 KB Output is correct
22 Correct 765 ms 50344 KB Output is correct
23 Correct 778 ms 50272 KB Output is correct
24 Correct 342 ms 50260 KB Output is correct
25 Correct 416 ms 50256 KB Output is correct
26 Correct 533 ms 50516 KB Output is correct
27 Correct 503 ms 50256 KB Output is correct
28 Correct 748 ms 50260 KB Output is correct
29 Correct 786 ms 50144 KB Output is correct
30 Correct 769 ms 50512 KB Output is correct
31 Correct 788 ms 50348 KB Output is correct
32 Correct 764 ms 50148 KB Output is correct
33 Incorrect 187 ms 43348 KB Output isn't correct
34 Halted 0 ms 0 KB -