oj.uz

Submission #600941

# Submission time Handle Problem Language Result Execution time Memory
600941 2022-07-21T09:22:38 Z Mazaalai Werewolf (IOI18_werewolf) C++17
34 / 100
 1093 ms 100692 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sz(x) (int)x.size()
using namespace std;
using VI = vector <int>;
using PII = pair <int, int>;
const int N = 2e5+1;
const int M = 3*N;
int n, m, q;
vector <int> paths[N];
int ans[N], p[N];
VI nums, res;
PII dp[N][20];
void dfs(int pos, int par = -1) {
    // cout << pos << " ";
    p[pos] = sz(nums);
    dp[p[pos]][0] = {pos, pos};
    nums.pb(pos);
    for (auto el : paths[pos]) {
        if (el == par) continue;
        dfs(el, pos);
    }
}
bool intersect(PII a, PII b) {
    int x = a.ss - a.ff + 1;
    int y = b.ss - b.ff + 1;
    int l = min(a.ff, b.ff);
    int r = max(a.ss, b.ss);
    l = r - l + 1;
    // cout << x << ' ' << y << ' ' << l << '\n';
    return (x+y > l);
}
PII get(int l, int r) {
    int p = 0, len = r - l + 1;
    while((1<<p) <= len) p++;
    p--;
    return {
        min(dp[l][p].ff, dp[r-(1<<p)+1][p].ff),
        max(dp[l][p].ss, dp[r-(1<<p)+1][p].ss)
    };
}
VI check_validity(int _N, VI X, VI Y, VI ST, VI ED, VI L, VI R) {
    n = _N;
    m = sz(X);
    q = sz(ST);
    for (int i = 0; i < m; i++) {
        paths[X[i]].pb(Y[i]);
        paths[Y[i]].pb(X[i]);
    }
    int st = 0;
    while(sz(paths[st]) != 1) st++;
    dfs(st); 
    for (int j = 1; j < 20; j++)
    for (int i = 0; i < n; i++) {
        dp[i][j] = {
            min(dp[i][j-1].ff, dp[min(n-1, i+(1<<(j-1)))][j-1].ff),
            max(dp[i][j-1].ss, dp[min(n-1, i+(1<<(j-1)))][j-1].ss)
        };
    }
    for (int i = 0; i < q; i++) {
        int a, b, c, d;
        a = b = ST[i] = p[ST[i]];
        c = d = ED[i] = p[ED[i]];
        {
            int l = 0, r = ST[i];
            while(l <= r) {
                int mid = (l+r)>>1;
                PII cur = get(mid, ST[i]);
                if (cur.ff >= L[i]) {
                    a = mid;
                    r = mid-1;
                } else {
                    l = mid+1;
                }
            }
        }
        {
            int l = ST[i], r = n-1;
            while(l <= r) {
                int mid = (l+r)>>1;
                PII cur = get(ST[i], mid);
                if (cur.ff >= L[i]) {
                    b = mid;
                    l = mid+1;
                } else {
                    r = mid-1;
                }
            }
        }
        {
            int l = 0, r = ED[i];
            while(l <= r) {
                int mid = (l+r)>>1;
                PII cur = get(mid, ED[i]);
                if (cur.ss <= R[i]) {
                    c = mid;
                    r = mid-1;
                } else {
                    l = mid+1;
                }
            }
        }
        {
            int l = ED[i], r = n-1;
            while(l <= r) {
                int mid = (l+r)>>1;
                PII cur = get(ED[i], mid);
                if (cur.ss <= R[i]) {
                    d = mid;
                    l=mid+1;
                } else {
                    r = mid-1;
                }
            }
        }
        // cout << ST[i] << " " << ED[i] << '\n';
        // cout << get(c, ED[i]).ss << " " << get(ED[i], d).ss << ' ' << R[i] << '\n';
        // cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';
        res.pb(intersect({a, b}, {c, d}));
    }
    return res;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 69 ms 100692 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 69 ms 100692 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 979 ms 64648 KB Output is correct
2 Correct 1004 ms 64776 KB Output is correct
3 Correct 1008 ms 64564 KB Output is correct
4 Correct 1033 ms 64584 KB Output is correct
5 Correct 996 ms 64712 KB Output is correct
6 Correct 1060 ms 64604 KB Output is correct
7 Correct 998 ms 64552 KB Output is correct
8 Correct 817 ms 64652 KB Output is correct
9 Correct 586 ms 64556 KB Output is correct
10 Correct 551 ms 64708 KB Output is correct
11 Correct 742 ms 64756 KB Output is correct
12 Correct 482 ms 64564 KB Output is correct
13 Correct 1093 ms 64580 KB Output is correct
14 Correct 1087 ms 64732 KB Output is correct
15 Correct 1039 ms 64688 KB Output is correct
16 Correct 1066 ms 64632 KB Output is correct
17 Correct 1016 ms 64644 KB Output is correct

Subtask #4
0 / 51.0

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