Submission #1110725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110725		underwaterkillerwhale	Werewolf (IOI18_werewolf)	C++17	100 / 100	452 ms	112876 KiB

werewolf

#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define REB(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 2e5 + 7;
const int N2 = 4e5 + 7;
const int Mod = 1e9 + 7;///lon
const ll INF = 1e18 + 7;
const int BASE = 137;
const int szBL = 350;

struct Query {
    int S, T, L, R;
};
struct Data {
    int L, R, L2, R2;
};

int n, m, Q;
vector<int> ke[N];
Query qr[N];
vector<int> events[N];

///KRT
int root;
int ein[N2], eout[N2];
vector<int> adj[N2];

int S[N2], T[N2];
pii RangeS[N2], RangeT[N2];

int Ans[N];
int inS[N2];
vector<pii> events_in_T[N2];

struct Disjoin_set {
    int nNode;
    int lab[N2];

    void init (int n) {
        rep (i, 1, n) {
            lab[i] = i;
        }
        nNode = n;
    }
    int Find (int u) {
        return u == lab[u] ? u : lab[u] = Find(lab[u]);
    }
    void Join (int u, int v, int typ) {
        u = Find(u);
        v = Find(v);
        if (u == v)
            return;
        ++nNode;
        if (typ == 1) {
            adj[nNode].pb(v);
            adj[nNode].pb(u);
        }
        lab[u] = lab[v] = lab[nNode] = nNode;
    }
}DSU;

struct Fenwick_Tree {
    int m;
    int fen[N2];

    void init (int n) {
        m = n;
    }
    void update (int pos, int val) {
        for (; pos <= m; pos += pos & -pos) fen[pos] += val;
    }
    int get (int pos) {
        int res = 0;
        for (;pos > 0; pos -= pos & -pos) res += fen[pos];
        return res;
    }
    int get (int L, int R) {
        return get(R) - get(L - 1);
    }
}BIT;

vector<int> process () {
    auto make_Tree = [&] (int typ) {
        rep (i, 1, n) vector<int> ().swap(events[i]);
        rep (i, 1, Q) {
            if (typ == 1) events[qr[i].R].pb(i);
            else events[qr[i].L].pb(i);
        }
        DSU.init(n);
        rep (i, 1, 2 * n) vector<int> ().swap(adj[i]);
        {
            int u = typ == -1 ? n : 1;
            while (u <= n && u >= 1) {
                iter (&v, ke[u]) {
                    if ((typ == -1 && v >= u) || (typ == 1 && v <= u))
                        DSU.Join(u, v, 1);
                }
                u += typ;
            }
        }
        root = DSU.Find(1);
        int time_dfs = 0;
        function<void(int, int)> pdfs = [&] (int u, int p) {
            ein[u] = ++time_dfs;
            if (typ == -1) S[ein[u]] = u;
            else T[ein[u]] = u;
            iter (&v, adj[u]) {
                if (v != p) {
                pdfs(v, u);
                }
            }
            eout[u] = time_dfs;
        };
        pdfs(root, 0);
        {
            DSU.init(n);
            int u = typ == -1 ? n : 1;
            while (u <= n && u >= 1) {
                iter (&v, ke[u]) {
                    if ((typ == -1 && v >= u) || (typ == 1 && v <= u))
                        DSU.Join(u, v, 0);
                }
                iter (&id, events[u]) {
                    int start = (typ == 1 ? qr[id].T : qr[id].S);
                    int Anc = DSU.Find(start);
                    if (typ == 1) RangeT[id] = {ein[Anc], eout[Anc]};
                    else RangeS[id] = {ein[Anc], eout[Anc]};
                }
                u += typ;
            }
        }
    };
    make_Tree(-1);
    make_Tree(1);
//    rep (i, 1, 2 * n) cout << S[i]<<" \n"[i == 2 *n];
//    rep (i, 1, 2 * n) cout << T[i]<<" \n"[i == 2 *n];
//    rep (i, 1, Q) cout << RangeS[i].fs <<","<<RangeS[i].se<<" "<<RangeT[i].fs <<","<<RangeT[i].se<<"\n";
    ///calc
    rep (i, 1, 2 * n) if (S[i] <= n && S[i] >= 1) inS[S[i]] = i;
    rep (i, 1, Q) {
        events_in_T[RangeT[i].fs - 1].pb({i, -1});
        events_in_T[RangeT[i].se].pb({i, 1});
    }
    BIT.init(2 * n);
    rep (i, 1, 2 * n) {
        if (T[i] <= n && T[i] >= 1) BIT.update(inS[T[i]], 1);
        iter (&id, events_in_T[i]) {
            int idx = id.fs, sign = id.se;
            int L, R;
            tie(L, R) = RangeS[idx];
            Ans[idx] += sign * BIT.get(L, R);
        }
    }
    vector<int> res;
    rep (i, 1, Q) {
        res.pb(Ans[i] > 0);
//        cout << Ans[i]<<"\n";
    }
    return res;
}

vector<int> check_validity(int _n, vector<int> X, vector<int> Y, vector<int> _S, vector<int> _E, vector<int> _L, vector<int> _R) {
    n = _n;
    m = SZ(X);
    rep (i, 1, m) {
        int u = X[i - 1], v = Y[i - 1];
        ++u, ++v;
        ke[u].pb(v);
        ke[v].pb(u);
    }
    Q = SZ(_S);
    rep (i, 1, Q) {
        qr[i].S = _S[i - 1];
        qr[i].T = _E[i - 1];
        qr[i].L = _L[i - 1];
        qr[i].R = _R[i - 1];
        ++qr[i].S, ++qr[i].T, ++qr[i].L, ++qr[i].R;
    }
    return process();
}

//#define file(name) if(fopen(name".inp","r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
//main () {
//    vector<int> cur = check_validity(6, {5, 1, 1, 3, 3, 5}, {1, 2, 3, 4, 0, 2}, {4, 4, 5}, {2, 2, 4}, {1, 2, 3}, {2, 2, 4});
//    iter (&id, cur) cout << id <<"\n";
////    file("c");
//    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
//    int num_Test = 1;
////    cin >> num_Test;
//    while (num_Test--) {
//        process();
//    }
//}
/*
onepunch +25

chắt lọc thông tin để mô hình
cận trên dưới
*/

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