Submission #594798

#	Time	Username	Problem	Language	Result	Execution time	Memory
594798		SlavicG	Werewolf (IOI18_werewolf)	C++17	0 / 100	553 ms	77876 KiB

werewolf

#include "bits/stdc++.h"
using namespace std;

#define ll long long

#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()

#define            pb                push_back
#define          sz(a)               (int)a.size()

template<typename T, bool zero_indexing>
struct fenwick_tree {
    int N;
    vector<T> fen;
    fenwick_tree(int n) {
        N = n, fen.assign(n + 1, 0);
    }
    fenwick_tree(vector<T> a) {
        N = a.size();
        fen.assign(N + 1, 0);
        for(int i = 0; i < N; ++i) {
            add(i, a[i]);
        }
    }
    void add(int p, T val) {
        for(int i = p + zero_indexing;i <= N;i += i & -i) {
            fen[i] += val;
        }
    }
    void set(int p, T val) {
        T set_val = val - query(p, p);
        add(p, set_val);
    }

    T query(int l, int r) {
        T ret = 0;
        for(int i = r + zero_indexing; i >= 1; i -= i & -i) {
            ret += fen[i];
        }
        for(int i = l + zero_indexing - 1; i >= 1; i -= i & -i) {
            ret -= fen[i];
        }
        return ret;
    }
};
const int N = 2e5 + 10;
int d[N], s1[N], s2[N], in1[N], in2[N], f1 = 0, f2 = 0;
vector<int> g1[N], g2[N];

int get(int a) {
    return d[a] = (d[a] == a ? a : get(d[a]));
}

void dfs1(int u) {
    s1[u] = 1;
    in1[u] = f1++;
    for(int v: g1[u]) {
        dfs1(v);
        s1[u] += s1[v];
    }
}
void dfs2(int u) {
    s2[u] = 1;
    in2[u] = f2++;
    for(int v: g2[u]) {
        dfs2(v);
        s2[u] += s2[v];
    }
}

vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
    forn(i, N) d[i] = i;
    int m = sz(x), q = sz(l);
    vector<vector<int>> edges(n);
    vector<int> root1(q), root2(q);
    vector<int> ss[n + 5], ee[n + 5];
    for(int i = 0;i < m; ++i) {
        edges[x[i]].pb(y[i]);
        edges[y[i]].pb(x[i]);
    }
    for(int i = 0;i < q; ++i) {
        ss[l[i]].pb(i);
        ee[r[i]].pb(i);
    }

    for(int i = n - 1; i >= 0; --i) {
        set<int> st;
        for(int v: edges[i]) {
            if(v < i) continue;
            st.insert(get(v));
        }

        for(auto x: st) {
            g1[i].pb(x);
            d[x] = i;
        }

        for(auto x: ss[i]) root1[x] = get(s[x]);
    }


    forn(i, N) d[i] = i;
    for(int i = 0; i < n; ++i) {
        set<int> st;
        for(int v: edges[i]) {
            if(v > i) continue;
            st.insert(get(v));
        }

        for(auto x: st) {
            g2[i].pb(x);
            d[x] = i;
        }

        for(auto x: ee[i]) {
            root2[x] = get(e[x]);
        }
    }

    dfs1(0);
    dfs2(n - 1);
    for(int i = 0; i < n; ++i) {
        assert(s1[i] > 0);
    }
    for(int i = n - 1; i >= 0; --i) {
        assert(s2[i] > 0);
    }

    vector<int> revin(n);
    for(int i = 0; i < n; ++i) {
        revin[in1[i]] = i;
    }
    vector<int> event[n], noo[n];
    for(int i = 0; i < q; ++i) {
        int node = root1[i];
        event[in1[node]].push_back(-1);
        event[in1[node] + s1[node] - 1].push_back(i);
        noo[in1[node] + s1[node] - 1].push_back(node);
    }
    vector<int> ans(q, 0);
    fenwick_tree<int, 1> fen(N);
    for(int i = 0; i < n; ++i) {
        sort(all(event[i]));
        for(auto x: event[i]) {
            if(x < 0) {
                fen.add(in2[revin[i]], 1);
            } else {
                int j = x;
                int node = root2[j];
                if(fen.query(in2[node], in2[node] + s2[node] - 1) > 0) {
                    ans[j] = 1;
                    cout << j << " " << ans[j] << "\n";
                }
            }
        }
        for(auto x: noo[i]) {
            fen.add(in2[x], -1);
        }
    }
    return ans;
}
/*
6 6 3
0 3
3 1
1 2
2 5
3 4
1 5
4 2 1 2
4 2 2 2
5 4 3 4
*/

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