Submission #1110321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110321		underwaterkillerwhale	Werewolf (IOI18_werewolf)	C++17	100 / 100	436 ms	118412 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 = 5e5 + 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> 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;
    }

//}
//void process () {
//    cin >> n >> m >> Q;
//    rep (i, 1, m) {
//        int u, v;
//        cin >> u >> v;
//        ++u, ++v;
//        ke[u].pb(v);
//        ke[v].pb(u);
//    }
//    rep (i, 1, Q) {
//        cin >> qr[i].S >> qr[i].T >> qr[i].L >> qr[i].R;
//        ++qr[i].S, ++qr[i].T, ++qr[i].L, ++qr[i].R;
//    }
    rep (i, 1, n) vector<int> ().swap(events[i]);
    rep (i, 1, Q) {
        events[qr[i].L].pb(i);
    }
    ///make_Tree1
    {
        DSU.init(n);
        rep (i, 1, n) vector<int> ().swap(adj[i]);
        REB (u, n, 1) {
            iter (&v, ke[u]) {
                if (v >= u) DSU.Join(u, v, 1);
            }
        }
        root = DSU.Find(1);
        int time_dfs = 0;
        function<void(int, int)> pdfs = [&] (int u, int p) {
            ein[u] = ++time_dfs;
            S[ein[u]] = u;
            iter (&v, adj[u]) {
                if (v != p) {
                pdfs(v, u);
                }
            }
            eout[u] = time_dfs;
        };
        pdfs(root, 0);
    }
    DSU.init(n);
    REB (u, n, 1) {
        iter (&v, ke[u]) {
            if (v >= u) DSU.Join(u, v, 0);
        }
        iter (&id, events[u]) {
            int Anc = DSU.Find(qr[id].S);
            RangeS[id] = {ein[Anc], eout[Anc]};
        }
    }
    rep (i, 1, n) vector<int> ().swap(events[i]);
    rep (i, 1, Q) {
        events[qr[i].R].pb(i);
    }
    ///make_Tree2
    {
        DSU.init(n);
        rep (i, 1, 2 * n) vector<int> ().swap(adj[i]);
        rep (u, 1, n) {
            iter (&v, ke[u]) {
                if (v <= u) DSU.Join(u, v, 1);
            }
        }
        root = DSU.Find(1);
        int time_dfs = 0;
        function<void(int, int)> pdfs = [&] (int u, int p) {
            ein[u] = ++time_dfs;
            T[ein[u]] = u;
            iter (&v, adj[u]) {
                if (v != p) {
                    pdfs(v, u);
                }
            }
            eout[u] = time_dfs;
        };
        pdfs(root, 0);
    }
    DSU.init(n);
    rep (u, 1, n) {
        iter (&v, ke[u]) {
            if (v <= u) DSU.Join(u, v, 0);
        }
        iter (&id, events[u]) {
            int Anc = DSU.Find(qr[id].T);
            RangeT[id] = {ein[Anc], eout[Anc]};
        }
    }
//    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;
}

//#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();
//    }
//}
/*
no bug challenge +24
10
T.*S..##S#
**###T#T.S
.*S.*.##T#

6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
10
T.*S..##S#
**###T#T.S
.*S.*.##T#
xử lí khéo hay
cận trên để giảm không gian và thời gian của mô hình bài toán
cận dưới để có thêm insight về kết quả bài toán

gọi sao cho có lợi cho mình nhất
*/

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