oj.uz

Submission #1110322

# Submission time Handle Problem Language Result Execution time Memory
1110322 2024-11-09T08:35:07 Z underwaterkillerwhale Werewolf (IOI18_werewolf) C++17
100 / 100
 442 ms 104016 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 = 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 () {
//    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;
}

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

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

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 47440 KB Output is correct
2 Correct 8 ms 47440 KB Output is correct
3 Correct 8 ms 47516 KB Output is correct
4 Correct 8 ms 47440 KB Output is correct
5 Correct 9 ms 47440 KB Output is correct
6 Correct 8 ms 47440 KB Output is correct
7 Correct 8 ms 47440 KB Output is correct
8 Correct 9 ms 47456 KB Output is correct
9 Correct 12 ms 47488 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 47440 KB Output is correct
2 Correct 8 ms 47440 KB Output is correct
3 Correct 8 ms 47516 KB Output is correct
4 Correct 8 ms 47440 KB Output is correct
5 Correct 9 ms 47440 KB Output is correct
6 Correct 8 ms 47440 KB Output is correct
7 Correct 8 ms 47440 KB Output is correct
8 Correct 9 ms 47456 KB Output is correct
9 Correct 12 ms 47488 KB Output is correct
10 Correct 13 ms 48208 KB Output is correct
11 Correct 13 ms 46416 KB Output is correct
12 Correct 12 ms 47952 KB Output is correct
13 Correct 14 ms 48208 KB Output is correct
14 Correct 15 ms 46416 KB Output is correct
15 Correct 14 ms 44128 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 82880 KB Output is correct
2 Correct 345 ms 93888 KB Output is correct
3 Correct 332 ms 84680 KB Output is correct
4 Correct 335 ms 78456 KB Output is correct
5 Correct 353 ms 85704 KB Output is correct
6 Correct 384 ms 83692 KB Output is correct
7 Correct 337 ms 84200 KB Output is correct
8 Correct 341 ms 97768 KB Output is correct
9 Correct 314 ms 87056 KB Output is correct
10 Correct 326 ms 85224 KB Output is correct
11 Correct 308 ms 83392 KB Output is correct
12 Correct 335 ms 81132 KB Output is correct
13 Correct 335 ms 92104 KB Output is correct
14 Correct 333 ms 89624 KB Output is correct
15 Correct 330 ms 89476 KB Output is correct
16 Correct 361 ms 95108 KB Output is correct
17 Correct 357 ms 83124 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 47440 KB Output is correct
2 Correct 8 ms 47440 KB Output is correct
3 Correct 8 ms 47516 KB Output is correct
4 Correct 8 ms 47440 KB Output is correct
5 Correct 9 ms 47440 KB Output is correct
6 Correct 8 ms 47440 KB Output is correct
7 Correct 8 ms 47440 KB Output is correct
8 Correct 9 ms 47456 KB Output is correct
9 Correct 12 ms 47488 KB Output is correct
10 Correct 13 ms 48208 KB Output is correct
11 Correct 13 ms 46416 KB Output is correct
12 Correct 12 ms 47952 KB Output is correct
13 Correct 14 ms 48208 KB Output is correct
14 Correct 15 ms 46416 KB Output is correct
15 Correct 14 ms 44128 KB Output is correct
16 Correct 341 ms 82880 KB Output is correct
17 Correct 345 ms 93888 KB Output is correct
18 Correct 332 ms 84680 KB Output is correct
19 Correct 335 ms 78456 KB Output is correct
20 Correct 353 ms 85704 KB Output is correct
21 Correct 384 ms 83692 KB Output is correct
22 Correct 337 ms 84200 KB Output is correct
23 Correct 341 ms 97768 KB Output is correct
24 Correct 314 ms 87056 KB Output is correct
25 Correct 326 ms 85224 KB Output is correct
26 Correct 308 ms 83392 KB Output is correct
27 Correct 335 ms 81132 KB Output is correct
28 Correct 335 ms 92104 KB Output is correct
29 Correct 333 ms 89624 KB Output is correct
30 Correct 330 ms 89476 KB Output is correct
31 Correct 361 ms 95108 KB Output is correct
32 Correct 357 ms 83124 KB Output is correct
33 Correct 383 ms 85696 KB Output is correct
34 Correct 209 ms 75036 KB Output is correct
35 Correct 388 ms 91480 KB Output is correct
36 Correct 377 ms 84416 KB Output is correct
37 Correct 436 ms 94824 KB Output is correct
38 Correct 392 ms 90048 KB Output is correct
39 Correct 389 ms 102148 KB Output is correct
40 Correct 432 ms 88296 KB Output is correct
41 Correct 378 ms 85204 KB Output is correct
42 Correct 319 ms 82488 KB Output is correct
43 Correct 442 ms 94400 KB Output is correct
44 Correct 390 ms 93068 KB Output is correct
45 Correct 383 ms 101328 KB Output is correct
46 Correct 403 ms 104016 KB Output is correct
47 Correct 344 ms 96960 KB Output is correct
48 Correct 339 ms 93892 KB Output is correct
49 Correct 343 ms 92324 KB Output is correct
50 Correct 345 ms 96456 KB Output is correct
51 Correct 424 ms 88012 KB Output is correct
52 Correct 412 ms 88256 KB Output is correct