Submission #600890

#	Time	Username	Problem	Language	Result	Execution time	Memory
600890		Mazaalai	Werewolf (IOI18_werewolf)	C++17	0 / 100	310 ms	524288 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;
struct Node {
    int mn, mx;
} node[M];

void build(int l, int r, int head) {
    if (l == r) {
        node[head] = {nums[l], nums[l]};
        return;
    }
    int mid = (l+r)>>1;
    build(l, mid, head*2+1);
    build(mid+1, r, head*2+2);
    node[head] = {min(node[head*2+1].mn, node[head*2+2].mn), max(node[head*2+1].mx, node[head*2+2].mx)};
}
void dfs(int pos, int par = -1) {
    // cout << pos << " ";
    p[pos] = sz(nums);
    nums.pb(pos);
    for (auto el : paths[pos]) {
        if (el == par) continue;
        dfs(el, pos);
    }
}
int middle(PII a, int b) {
    return (a.ff <= b && b <= a.ss);
}
PII zero = {1e9, -1e9};
PII merge(PII a, PII b, int l, int r, int pos) {
    if (a == zero) a = b;
    if (b == zero) b = a;
    if (a == b && b == zero) return zero;
    if (a.ss+1 == b.ff) {
        a.ss = b.ss;
        if (middle(a, pos)) return a;
        if (r < pos && a.ss == r) return a;
        if (pos < l && a.ff == l) return a;
        return zero;
    }
    if (middle(mp(l, r), pos)) {
        if (middle(a, pos)) return a;
        if (middle(b, pos)) return b;
        return zero;
    }
    if (r < pos) {
        if (b.ss == r) return b;
        return zero;
    }
    // pos < l
    if (a.ff == l) return a;
    return zero;
}
PII getBoundaryA(int l, int r, int pos, int lim, int head) { // human
    if (node[head].mx < lim) return zero;
    if (node[head].mn >= lim) return {l, r};
    int mid = (l+r)>>1;
    // PII a = getBoundaryA(l, mid, pos, lim, head*2+1);
    // PII b = getBoundaryA(mid+1, r, pos, lim, head*2+2);
    // return merge(a, b, l, r, pos);
    return zero;
}
PII getBoundaryB(int l, int r, int pos, int lim, int head) { // wolf
    if (node[head].mn > lim) {
        PII c = zero;
        return zero;
    }
    if (node[head].mx <= lim) {
        PII c = {l, r};
        return {l, r};
    }
    int mid = (l+r)>>1;
    PII a = getBoundaryB(l, mid, pos, lim, head*2+1);
    PII b = getBoundaryB(mid+1, r, pos, lim, head*2+2);
    PII c = merge(a, b, l, r, pos);
    return merge(a, b, l, r, 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 = min(a.ss, b.ss);
    l = r - l + 1;
    return (x+y > l);
}
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);
    // cout << "\n";
    build(0, n-1, 0);
    for (int i = 0; i < q; i++) {
        PII a = getBoundaryA(0, n-1, p[ST[i]], L[i], 0);
        // PII b = getBoundaryB(0, n-1, p[ED[i]], R[i], 0);
        // cout << a.ff << ' ' << a.ss << ' ';
        // cout << b.ff << ' ' << b.ss << '\n';
        // res.pb(intersect(a, b));

    }
    return res;
}

Compilation message (stderr)

werewolf.cpp: In function 'PII getBoundaryA(int, int, int, int, int)':
werewolf.cpp:71:9: warning: unused variable 'mid' [-Wunused-variable]
   71 |     int mid = (l+r)>>1;
      |         ^~~
werewolf.cpp: In function 'PII getBoundaryB(int, int, int, int, int)':
werewolf.cpp:79:13: warning: variable 'c' set but not used [-Wunused-but-set-variable]
   79 |         PII c = zero;
      |             ^
werewolf.cpp:83:13: warning: variable 'c' set but not used [-Wunused-but-set-variable]
   83 |         PII c = {l, r};
      |             ^
werewolf.cpp:89:9: warning: variable 'c' set but not used [-Wunused-but-set-variable]
   89 |     PII c = merge(a, b, l, r, pos);
      |         ^
werewolf.cpp: In function 'VI check_validity(int, VI, VI, VI, VI, VI, VI)':
werewolf.cpp:114:13: warning: variable 'a' set but not used [-Wunused-but-set-variable]
  114 |         PII a = getBoundaryA(0, n-1, p[ST[i]], L[i], 0);
      |             ^

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51