Submission #600093

#	Time	Username	Problem	Language	Result	Execution time	Memory
600093		MohamedFaresNebili	Werewolf (IOI18_werewolf)	C++14	100 / 100	713 ms	87780 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")

                using namespace std;

                using ll = long long;
                using ld = long double;
                using ii = pair<ll, ll>;
                using vi = vector<int>;

                #define ff first
                #define ss second
                #define pb push_back
                #define all(x) (x).begin(), (x).end()
                #define lb lower_bound

                const int MOD = 1e9 + 7;

                int P[200005][2];
                int W[200005], timer;
                vector<int> adj[200005];
                vector<int> G[200005][2];
                vector<int> A[200005], B[200005];
                int tin[200005][2], out[200005][2];
                int st[800005], D[200005], K[200005];

                int query(int v, int l, int r, int lo, int hi) {
                    if(l > hi || r < lo) return 0;
                    if(l >= lo && r <= hi) return st[v];
                    return query(v * 2, l, (l + r) / 2, lo, hi)
                        +  query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi);
                }
                void update(int v, int l, int r, int p) {
                    if(l == r) {
                        st[v]++;
                        return;
                    }
                    int md = (l + r) / 2;
                    if(p <= md) update(v * 2, l, md, p);
                    else update(v * 2 + 1, md + 1, r, p);
                    st[v] = st[v * 2] + st[v * 2 + 1];
                }
                int findSet(int v, int s) {
                    if(P[v][s] == v) return v;
                    return P[v][s] = findSet(P[v][s], s);
                }
                void unionSet(int u, int v, int s) {
                    u = findSet(u, s), v = findSet(v, s);
                    if(u == v) return;
                    P[v][s] = u;
                }
                void dfs(int v, int p) {
                    tin[v][p] = timer++;
                    for(auto u : G[v][p])
                        dfs(u, p);
                    out[v][p] = timer - 1;
                }

                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(), Q = S.size();
                    for(int l = 0; l < N; l++)
                        P[l][0] = P[l][1] = l;
                    for(int l = 0; l < M; l++) {
                        int U = X[l], V = Y[l];
                        adj[U].push_back(V);
                        adj[V].push_back(U);
                    }
                    for(int l = 0; l < Q; l++) {
                        A[L[l]].push_back(l);
                        B[R[l]].push_back(l);
                    }
                    for(int l = N - 1; l >= 0; l--) {
                        for(auto u : adj[l]) {
                            if(u < l || findSet(u, 0) == l) continue;
                            G[l][0].push_back(findSet(u, 0));
                            unionSet(l, u, 0);
                        }
                        for(auto u : A[l]) D[u] = findSet(S[u], 0);
                    }
                    for(int l = 0; l < N; l++) {
                        for(auto u : adj[l]) {
                            if(u > l || findSet(u, 1) == l) continue;
                            G[l][1].push_back(findSet(u, 1));
                            unionSet(l, u, 1);
                        }
                        for(auto u : B[l]) K[u] = findSet(E[u], 1);
                    }
                    dfs(0, 0); timer = 0; dfs(N - 1, 1);
                    vector<int> Qr[N];
                    vector<int> res(Q, 0);

                    for(int l = 0; l < Q; l++) {
                        int v = D[l];
                        Qr[tin[v][0]].push_back(-l - 1);
                        Qr[out[v][0]].push_back(l);
                    }
                    for(int l = 0; l < N; l++) {
                        W[tin[l][0]] = tin[l][1];
                    }
                    for(int l = 0; l < N; l++) {
                        for(auto u : Qr[l]) {
                            if(u >= 0) continue;
                            int v = -u - 1; int C = K[v];
                            res[v] -= query(1, 0, N - 1, tin[C][1], out[C][1]);
                        }
                        update(1, 0, N - 1, W[l]);
                        for(auto u : Qr[l]) {
                            if(u < 0) continue;
                            int C = K[u];
                            res[u] += query(1, 0, N - 1, tin[C][1], out[C][1]);
                        }
                    }
                    for(int l = 0; l < Q; l++)
                        res[l] = min(res[l], 1);
                    return res;
                }

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