Submission #1038103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038103		RecursiveCo	Werewolf (IOI18_werewolf)	C++17	34 / 100	406 ms	61240 KiB

werewolf

#include <bits/stdc++.h>

using namespace std;

#define in(i) cin >> i
#define out(o) cout << o

vector<int> parent;
vector<int> sz;

int find(int v) {
    if (v == parent[v]) return v;
    return parent[v] = find(parent[v]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    if (sz[a] > sz[b]) swap(a, b);
    parent[a] = b;
    sz[b] += sz[a];
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    int M = X.size(); // = Y.size()
    int Q = S.size(); // = E.size() = L.size() = R.size()
    parent.resize(N);
    sz.resize(N, 1);
    vector<int> ans(Q);
    if (N <= 3000 && M <= 6000 && Q <= 3000 && false) {
        // S1, S2
        for (int i = 0; i < Q; i++) {
            int l = L[i];
            int r = R[i];
            int s = S[i];
            int e = E[i];

            for (int j = 0; j < N; j++) parent[j] = j, sz[j] = 1;
            for (int j = 0; j < M; j++) {
                int x = X[j];
                int y = Y[j];
                if (l <= min(x, y)) unite(x, y);
            }
            vector<int> works(N, 0);
            for (int j = 0; j < N; j++) if (find(s) == find(j)) works[j]++;

            for (int j = 0; j < N; j++) parent[j] = j, sz[j] = 1;
            for (int j = 0; j < M; j++) {
                int x = X[j];
                int y = Y[j];
                if (r >= max(x, y)) unite(x, y);
            }
            for (int j = 0; j < N; j++) if (find(e) == find(j)) works[j]++;
            ans[i] = +(*max_element(works.begin(), works.end()) == 2);
        }
    } else {
        // S3 assumed, if S4 then segfault or sth
        vector<vector<int>> adjList(N);
        for (int i = 0; i < M; i++) {
            int x = X[i];
            int y = Y[i];
            adjList[x].push_back(y);
            adjList[y].push_back(x);
        }
        int v = 0;
        int prev = -1;
        while (adjList[v].size() == 2) {
            if (adjList[v][0] == prev) {
                prev = v;
                v = adjList[v][1];
            } else {
                prev = v;
                v = adjList[v][0];
            }
        }
        vector<int> order;
        order.push_back(v);
        prev = -1;
        do {
            if (adjList[v][0] == prev) {
                prev = v;
                v = adjList[v][1];
            } else {
                prev = v;
                v = adjList[v][0];
            }
            order.push_back(v);
        } while (adjList[v].size() == 2);
        vector<int> ind(N);
        for (int i = 0; i < N; i++) {
            ind[order[i]] = i;
        }
        vector<int> left(Q);
        vector<int> right(Q);
        vector<array<int, 4>> human;
        vector<array<int, 4>> wolf;
        // {determiner, node, query index, left or right}. left = 0, right = 1.
        for (int i = 0; i < Q; i++) {
            int l = L[i];
            int r = R[i];
            int s = S[i];
            int e = E[i];
            int u = ind[s];
            int v = ind[e];
            if (u < v) {
                human.push_back({l, u, i, 1});
                wolf.push_back({r, v, i, 0});
            } else {
                human.push_back({l, u, i, 0});
                wolf.push_back({r, v, i, 1});
            }
        }
        sort(human.begin(), human.end());
        sort(wolf.rbegin(), wolf.rend());
        set<int> less;
        int ptr = 0;
        for (int i = 0; i < N; i++) {
            while (ptr < Q && human[ptr][0] <= i) {
                int l = human[ptr][0];
                int u = human[ptr][1];
                int j = human[ptr][2];
                int dir = human[ptr][3];
                if (dir) {
                    auto it = less.lower_bound(u);
                    if (it == less.end()) right[j] = N + 5;
                    else right[j] = (*it) - 1;
                } else {
                    auto it = less.lower_bound(u);
                    if (it == less.begin()) left[j] = -5;
                    else left[j] = (*--it) + 1;
                }
                ptr++;
            }
            less.insert(ind[i]);
        }
        set<int> more;
        ptr = 0;
        for (int i = N - 1; i >= 0; i--) {
            while (ptr < Q && wolf[ptr][0] >= i) {
                int l = wolf[ptr][0];
                int u = wolf[ptr][1];
                int j = wolf[ptr][2];
                int dir = wolf[ptr][3];
                if (dir) {
                    auto it = more.lower_bound(u);
                    if (it == more.end()) right[j] = N + 5;
                    else right[j] = (*it) - 1;
                } else {
                    auto it = more.lower_bound(u);
                    if (it == more.begin()) left[j] = -5;
                    else left[j] = (*--it) + 1;
                }
                ptr++;
            }
            more.insert(ind[i]);
        }
        for (int i = 0; i < Q; i++) {
            ans[i] = +(left[i] <= right[i]);
        }
    }
    return ans;
}

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:120:21: warning: unused variable 'l' [-Wunused-variable]
  120 |                 int l = human[ptr][0];
      |                     ^
werewolf.cpp:141:21: warning: unused variable 'l' [-Wunused-variable]
  141 |                 int l = wolf[ptr][0];
      |                     ^

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