Submission #600941

#	Time	Username	Problem	Language	Result	Execution time	Memory
600941		Mazaalai	Werewolf (IOI18_werewolf)	C++17	34 / 100	1093 ms	100692 KiB

werewolf

#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
• Subtask 2: 0 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51