oj.uz

Submission #1110321

# Submission time Handle Problem Language Result Execution time Memory
1110321 2024-11-09T08:31:03 Z underwaterkillerwhale Werewolf (IOI18_werewolf) C++17
100 / 100
 436 ms 118412 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 52304 KB Output is correct
2 Correct 9 ms 52476 KB Output is correct
3 Correct 8 ms 52372 KB Output is correct
4 Correct 9 ms 52304 KB Output is correct
5 Correct 9 ms 52304 KB Output is correct
6 Correct 9 ms 52420 KB Output is correct
7 Correct 9 ms 50256 KB Output is correct
8 Correct 8 ms 48384 KB Output is correct
9 Correct 8 ms 50256 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 52304 KB Output is correct
2 Correct 9 ms 52476 KB Output is correct
3 Correct 8 ms 52372 KB Output is correct
4 Correct 9 ms 52304 KB Output is correct
5 Correct 9 ms 52304 KB Output is correct
6 Correct 9 ms 52420 KB Output is correct
7 Correct 9 ms 50256 KB Output is correct
8 Correct 8 ms 48384 KB Output is correct
9 Correct 8 ms 50256 KB Output is correct
10 Correct 13 ms 53088 KB Output is correct
11 Correct 12 ms 53188 KB Output is correct
12 Correct 12 ms 51024 KB Output is correct
13 Correct 12 ms 47436 KB Output is correct
14 Correct 12 ms 51280 KB Output is correct
15 Correct 11 ms 43152 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 95612 KB Output is correct
2 Correct 315 ms 106888 KB Output is correct
3 Correct 349 ms 101576 KB Output is correct
4 Correct 345 ms 95424 KB Output is correct
5 Correct 335 ms 92052 KB Output is correct
6 Correct 385 ms 95368 KB Output is correct
7 Correct 328 ms 93928 KB Output is correct
8 Correct 320 ms 105152 KB Output is correct
9 Correct 323 ms 97336 KB Output is correct
10 Correct 322 ms 94220 KB Output is correct
11 Correct 341 ms 91256 KB Output is correct
12 Correct 337 ms 91864 KB Output is correct
13 Correct 341 ms 104784 KB Output is correct
14 Correct 322 ms 103432 KB Output is correct
15 Correct 313 ms 104900 KB Output is correct
16 Correct 308 ms 106440 KB Output is correct
17 Correct 294 ms 97288 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 52304 KB Output is correct
2 Correct 9 ms 52476 KB Output is correct
3 Correct 8 ms 52372 KB Output is correct
4 Correct 9 ms 52304 KB Output is correct
5 Correct 9 ms 52304 KB Output is correct
6 Correct 9 ms 52420 KB Output is correct
7 Correct 9 ms 50256 KB Output is correct
8 Correct 8 ms 48384 KB Output is correct
9 Correct 8 ms 50256 KB Output is correct
10 Correct 13 ms 53088 KB Output is correct
11 Correct 12 ms 53188 KB Output is correct
12 Correct 12 ms 51024 KB Output is correct
13 Correct 12 ms 47436 KB Output is correct
14 Correct 12 ms 51280 KB Output is correct
15 Correct 11 ms 43152 KB Output is correct
16 Correct 372 ms 95612 KB Output is correct
17 Correct 315 ms 106888 KB Output is correct
18 Correct 349 ms 101576 KB Output is correct
19 Correct 345 ms 95424 KB Output is correct
20 Correct 335 ms 92052 KB Output is correct
21 Correct 385 ms 95368 KB Output is correct
22 Correct 328 ms 93928 KB Output is correct
23 Correct 320 ms 105152 KB Output is correct
24 Correct 323 ms 97336 KB Output is correct
25 Correct 322 ms 94220 KB Output is correct
26 Correct 341 ms 91256 KB Output is correct
27 Correct 337 ms 91864 KB Output is correct
28 Correct 341 ms 104784 KB Output is correct
29 Correct 322 ms 103432 KB Output is correct
30 Correct 313 ms 104900 KB Output is correct
31 Correct 308 ms 106440 KB Output is correct
32 Correct 294 ms 97288 KB Output is correct
33 Correct 365 ms 97444 KB Output is correct
34 Correct 189 ms 85248 KB Output is correct
35 Correct 431 ms 108512 KB Output is correct
36 Correct 370 ms 96968 KB Output is correct
37 Correct 436 ms 103616 KB Output is correct
38 Correct 413 ms 98496 KB Output is correct
39 Correct 401 ms 118412 KB Output is correct
40 Correct 434 ms 108224 KB Output is correct
41 Correct 352 ms 98260 KB Output is correct
42 Correct 308 ms 98208 KB Output is correct
43 Correct 406 ms 113424 KB Output is correct
44 Correct 388 ms 99496 KB Output is correct
45 Correct 378 ms 115044 KB Output is correct
46 Correct 401 ms 117956 KB Output is correct
47 Correct 355 ms 106688 KB Output is correct
48 Correct 347 ms 109508 KB Output is correct
49 Correct 346 ms 106692 KB Output is correct
50 Correct 357 ms 106408 KB Output is correct
51 Correct 434 ms 106800 KB Output is correct
52 Correct 429 ms 102304 KB Output is correct