Submission #594771

#	Time	Username	Problem	Language	Result	Execution time	Memory
594771		SlavicG	Werewolf (IOI18_werewolf)	C++17	0 / 100	481 ms	62388 KiB

werewolf

#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;

const int N = 2e5 + 10;
ll fen[N];
void modif(int u, int val) {
    for(int i = u + 1; i < N; i += (i & -i)) fen[i] += val;
}
ll query(int l, int r) {
    assert(l <= r);
    ll ans = 0;
    for(int i = r + 1; i > 0; i -= (i & -i)) ans += fen[i];
    for(int i = l; i > 0; i -= (i & -i)) ans -= fen[i];
    return ans;
}

struct dsu {
    vector<int> p;
    dsu(int n) {
        p.resize(n); iota(p.begin(), p.end(), 0);
    }
    int get(int a) {
        return (a == p[a] ? a : get(p[a]));
    }
    void uni(int a, int b) {
        a = get(a), b = get(b);
        if(a == b) return;
        p[a] = b;
    }
};

void dfs(int u, vector<int>& p, vector<int>& s, vector<vector<int>>& adj, int& tt) {
    p[u] = tt++;
    s[u] = 1;
    for(int v: adj[u]) {
        dfs(v, p, s, adj, tt);
        s[u] += s[v];
    }
}

std::vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, std::vector<int> E,
vector<int> L, std::vector<int> R) {
    for(int i = 0; i < N; ++i) fen[i] = 0;
    int Q = S.size(), paiu = 0, moment = 0;
    vector<int> ans(Q, 0);
    vector<vector<int>> g1(n), g2(n), g(n);
    for(int i = 0; i < (int)X.size(); ++i) {
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    dsu d1(n), d2(n);

    for(int i = n - 1; i >= 0; --i) {
        set<int> st;
        for(int j: g[i]) {
            if(i < j && d1.get(i) != d1.get(j)) st.insert(d1.get(j));
        }
        for(auto x: st) {
            g1[i].push_back(d1.get(x));
            d1.uni(x, i);
        }
    }

    for(int i = 0; i < n; ++i) {
        set<int> st;
        for(int j: g[i]) {
            if(i > j && d2.get(i) != d2.get(j)) st.insert(d2.get(j));
        }
        for(auto x: st) {
            g2[i].push_back(d2.get(x));
            d2.uni(x, i);
        }
    }
    vector<int> p1(n, -1), s1(n), p2(n, -1), s2(n);
    dfs(0, p1, s1, g1, paiu);
    dfs(n - 1, p2, s2, g2, moment);
    for(int i = 0; i < n; ++i) {
        assert(p1[i] != -1 && p2[i] != -1);
    }
    vector<int> events[n], nodes(n);
    for(int i = 0; i < n; ++i) nodes[p1[i]] = p2[i];
    vector<int> to_delete[n];
    for(int i = 0; i < Q; ++i) {
        int node = L[i];
        events[p1[node]].push_back(-1);
        events[p1[node] + s1[node] - 1].push_back(i);
        to_delete[p1[node] + s1[node] - 1].push_back(p1[node]);
    }
    for(int i = 0; i < n; ++i) {
        sort(events[i].begin(), events[i].end());
        for(int j: events[i]) {
            if(j < 0) {
                modif(nodes[i], 1);
            } else {
                int node = R[j];
                int nodeL = L[j];
                assert(query(p2[node], p2[node] + s2[node] - 1) >= 0);
                if(query(p2[node], p2[node] + s2[node] - 1) > 0) {
                    if(p1[nodeL] <= p1[S[j]] && p1[S[j]] <= i && p2[node] <= p2[E[j]] && p2[E[j]] <= p2[node] + s2[node] - 1) {
                        ans[j] = 1;
                    }
                }
            }
        }
        for(int j: to_delete[i]) {
            if(j >= 0) {
                modif(nodes[j], -1);
            }
        }
    }
    return ans;
}

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