Submission #448114

#	Time	Username	Problem	Language	Result	Execution time	Memory
448114		MilosMilutinovic	Werewolf (IOI18_werewolf)	C++14	0 / 100	444 ms	524292 KiB

werewolf

#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
#define mod 123456789
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
ll ksm(ll a, ll b)  {if (b == 0) return 1; ll ns = ksm(a, b >> 1); ns = ns * ns % mod; if (b & 1) ns = ns * a % mod; return ns;}
using namespace std;
const int maxn = 200050;
const int lg = 20; // log2(maxn)
int n, m, q;
vi ed[maxn];
vi ord;
int mn[maxn][lg];
int mx[maxn][lg];
int logs[maxn];
void dfs(int u, int p) {
    ord.pb(u);
    for (int v : ed[u]) {
        if (v != p) {
            dfs(v, u);
        }
    }
}
void bld() {
    logs[1] = 0;
    for (int i = 2; i < maxn; i++) logs[i] = logs[i / 2] + 1;
    for (int i = 0; i < n; i++) {
        mn[i][0] = ord[i];
        mx[i][0] = ord[i];
    }
    for (int j = 1; j < lg; j++) {
        for (int i = 0; i + (1 << j) <= n; i++) {
            mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
            mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
        }
    }
}
int getmn(int l, int r) {
    int sz = logs[r - l + 1];
    return min(mn[l][sz], mn[r - (1 << sz) + 1][sz]);
}
int getmx(int l, int r) {
    int sz = logs[r - l + 1];
    return max(mx[l][sz], mx[r - (1 << sz) + 1][sz]);
}
int inter(pi X, pi Y) {
    if (X.se < Y.fi) return 0;
    if (X.fi > Y.se) return 0;
    return 1;
}
vi check_validity(int N, vi u, vi v, vi s, vi e, vi l, vi r) {
    n = N, m = u.size(), q = (int) s.size();
    for (int i = 0; i < m; i++) {
        ed[u[i]].pb(v[i]);
        ed[v[i]].pb(u[i]);
    }
    int st = 0;
    for (int i = 0; i < n; i++)
        if (ed[i].size() <= 1) st = i;
    dfs(st, st);
    assert((int) ord.size() == n);
    bld();
    vi res(n);
    for (int i = 0; i < q; i++) {
        pi x = {s[i], s[i]}, y = {e[i], e[i]};
        /*{
            int bot = 0, top = s[i] - 1;
            while (bot <= top) {
                int mid = bot + top >> 1;
                if (getmn(mid, s[i] - 1) >= l[i]) {
                    x.fi = mid;
                    top = mid - 1;
                } else bot = mid + 1;
            }
        }*/
        {
            int bot = s[i] + 1, top = n - 1;
            while (bot <= top) {
                int mid = bot + top >> 1;
                if (getmn(s[i] + 1, mid) >= l[i]) {
                    x.se = mid;
                    bot = mid + 1;
                } else top = mid - 1;
            }
        }
        /*{
            int bot = 0, top = e[i] - 1;
            while (bot <= top) {
                int mid = bot + top >> 1;
                if (getmx(mid, e[i] - 1) <= r[i]) {
                    y.fi = mid;
                    top = mid - 1;
                } else bot = mid + 1;
            }
        }
        {
            int bot = e[i] + 1, top = n - 1;
            while (bot <= top) {
                int mid = bot + top >> 1;
                if (getmx(e[i] + 1, mid) <= r[i]) {
                    y.se = mid;
                    bot = mid + 1;
                } else top = mid - 1;
            }
        }*/
        res[i] = inter(x, y);
    }
    return res;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:85:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |                 int mid = bot + top >> 1;
      |                           ~~~~^~~~~

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