Submission #1190000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190000		MatteoArcari	늑대인간 (IOI18_werewolf)	C++20	34 / 100	205 ms	38032 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;

struct Segtree {
    int n;
    vi ma, mi;
    Segtree (vi ord) {
        n = ord.size();
        ma.resize(4 * n);
        mi.resize(4 * n);
        build(1, 0, n, ord);
    }
    void build (int i, int sl, int sr, vi &ord) {
        if (sr - sl == 1) {
            mi[i] = ma[i] = ord[sl];
            return;
        }
        int mid = sl + sr >> 1;
        build(2 * i, sl, mid, ord);
        build(2 * i + 1, mid, sr, ord);
        mi[i] = min(mi[2 * i], mi[2 * i + 1]);
        ma[i] = max(ma[2 * i], ma[2 * i + 1]);
    }
    int getL (int i, int sl, int sr, int l, int t) {
        if (sr <= l) return n;
        if (mi[i] >= t) return n;
        if (sr - sl == 1) return sl;
        int mid = sl + sr >> 1;
        int ans = getL(2 * i, sl, mid, l, t);
        if (ans != n) return ans;
        return getL(2 * i + 1, mid, sr, l, t);
    }
    int getL (int i, int l) {
        return getL(1, 0, n, i, l); 
    }
    int getR (int i, int sl, int sr, int r, int t) {
        if (sl >= r) return -1;
        if (ma[i] <= t) return -1;
        if (sr - sl == 1) return sl;
        int mid = sl + sr >> 1;
        int ans = getR(2 * i + 1, mid, sr, r, t);
        if (ans != -1) return ans;
        return getR(2 * i, sl, mid, r, t);
    }
    int getR (int i, int r) {
        return getR(1, 0, n, i, r); 
    }
};

vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r) {
    int q = s.size();
    int m = x.size();
    vector<vi> adj(n);
    for (int i = 0; i < m; i++) {
        adj[x[i]].push_back(y[i]);
        adj[y[i]].push_back(x[i]);
    }

    vi ans(q);

    vi ord(n), pos(n);
    for (int i = 0; i < n; i++) {
        if (adj[i].size() == 1) {
            ord[0] = i;
            ord[1] = adj[i][0];
            pos[i] = 0;
            pos[adj[i][0]] = 1;
            break;
        }
    }
    for (int i = 1; i + 1 < n; i++) {
        int j = adj[ord[i]][0] ^ adj[ord[i]][1] ^ ord[i - 1];
        ord[i + 1] = j;
        pos[j] = i + 1;
    }

    vi rev_ord = ord; reverse(rev_ord.begin(), rev_ord.end());
    vi rev_pos(n); 
    for (int i = 0; i < n; i++) rev_pos[rev_ord[i]] = i;

    Segtree Ord(ord);
    Segtree Rev(rev_ord);

    for (int i = 0; i < q; i++) {
        int left, right;
        if (pos[s[i]] < pos[e[i]]) {
            left = Ord.getL(pos[s[i]], l[i]) - 1;
            right = Ord.getR(pos[e[i]], r[i]) + 1;
        } else {
            left = Rev.getL(rev_pos[s[i]], l[i]) - 1;
            right = Rev.getR(rev_pos[e[i]], r[i]) + 1;
        }
        ans[i] = left >= right;
    }

    return ans;
}

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