oj.uz

Submission #1110725

# Submission time Handle Problem Language Result Execution time Memory
1110725 2024-11-10T09:33:40 Z underwaterkillerwhale Werewolf (IOI18_werewolf) C++17
100 / 100
 452 ms 112876 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 () {
    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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 47440 KB Output is correct
2 Correct 8 ms 47544 KB Output is correct
3 Correct 8 ms 47440 KB Output is correct
4 Correct 8 ms 47440 KB Output is correct
5 Correct 8 ms 47448 KB Output is correct
6 Correct 8 ms 47440 KB Output is correct
7 Correct 9 ms 47608 KB Output is correct
8 Correct 8 ms 47440 KB Output is correct
9 Correct 8 ms 47440 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 47440 KB Output is correct
2 Correct 8 ms 47544 KB Output is correct
3 Correct 8 ms 47440 KB Output is correct
4 Correct 8 ms 47440 KB Output is correct
5 Correct 8 ms 47448 KB Output is correct
6 Correct 8 ms 47440 KB Output is correct
7 Correct 9 ms 47608 KB Output is correct
8 Correct 8 ms 47440 KB Output is correct
9 Correct 8 ms 47440 KB Output is correct
10 Correct 12 ms 48380 KB Output is correct
11 Correct 13 ms 46160 KB Output is correct
12 Correct 13 ms 48124 KB Output is correct
13 Correct 14 ms 48464 KB Output is correct
14 Correct 13 ms 44368 KB Output is correct
15 Correct 14 ms 42232 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 88680 KB Output is correct
2 Correct 341 ms 98752 KB Output is correct
3 Correct 348 ms 92360 KB Output is correct
4 Correct 354 ms 89792 KB Output is correct
5 Correct 341 ms 89704 KB Output is correct
6 Correct 357 ms 90580 KB Output is correct
7 Correct 324 ms 88036 KB Output is correct
8 Correct 333 ms 98752 KB Output is correct
9 Correct 311 ms 93496 KB Output is correct
10 Correct 287 ms 86976 KB Output is correct
11 Correct 301 ms 87656 KB Output is correct
12 Correct 314 ms 89396 KB Output is correct
13 Correct 334 ms 100552 KB Output is correct
14 Correct 359 ms 100468 KB Output is correct
15 Correct 363 ms 100588 KB Output is correct
16 Correct 327 ms 100560 KB Output is correct
17 Correct 342 ms 87472 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 47440 KB Output is correct
2 Correct 8 ms 47544 KB Output is correct
3 Correct 8 ms 47440 KB Output is correct
4 Correct 8 ms 47440 KB Output is correct
5 Correct 8 ms 47448 KB Output is correct
6 Correct 8 ms 47440 KB Output is correct
7 Correct 9 ms 47608 KB Output is correct
8 Correct 8 ms 47440 KB Output is correct
9 Correct 8 ms 47440 KB Output is correct
10 Correct 12 ms 48380 KB Output is correct
11 Correct 13 ms 46160 KB Output is correct
12 Correct 13 ms 48124 KB Output is correct
13 Correct 14 ms 48464 KB Output is correct
14 Correct 13 ms 44368 KB Output is correct
15 Correct 14 ms 42232 KB Output is correct
16 Correct 391 ms 88680 KB Output is correct
17 Correct 341 ms 98752 KB Output is correct
18 Correct 348 ms 92360 KB Output is correct
19 Correct 354 ms 89792 KB Output is correct
20 Correct 341 ms 89704 KB Output is correct
21 Correct 357 ms 90580 KB Output is correct
22 Correct 324 ms 88036 KB Output is correct
23 Correct 333 ms 98752 KB Output is correct
24 Correct 311 ms 93496 KB Output is correct
25 Correct 287 ms 86976 KB Output is correct
26 Correct 301 ms 87656 KB Output is correct
27 Correct 314 ms 89396 KB Output is correct
28 Correct 334 ms 100552 KB Output is correct
29 Correct 359 ms 100468 KB Output is correct
30 Correct 363 ms 100588 KB Output is correct
31 Correct 327 ms 100560 KB Output is correct
32 Correct 342 ms 87472 KB Output is correct
33 Correct 391 ms 93932 KB Output is correct
34 Correct 198 ms 86556 KB Output is correct
35 Correct 380 ms 100032 KB Output is correct
36 Correct 357 ms 89868 KB Output is correct
37 Correct 391 ms 95600 KB Output is correct
38 Correct 388 ms 90304 KB Output is correct
39 Correct 420 ms 109760 KB Output is correct
40 Correct 452 ms 98536 KB Output is correct
41 Correct 385 ms 95400 KB Output is correct
42 Correct 332 ms 90880 KB Output is correct
43 Correct 433 ms 104384 KB Output is correct
44 Correct 380 ms 97212 KB Output is correct
45 Correct 378 ms 112876 KB Output is correct
46 Correct 385 ms 112580 KB Output is correct
47 Correct 369 ms 100288 KB Output is correct
48 Correct 352 ms 100508 KB Output is correct
49 Correct 417 ms 100760 KB Output is correct
50 Correct 368 ms 99788 KB Output is correct
51 Correct 406 ms 99468 KB Output is correct
52 Correct 444 ms 99776 KB Output is correct