oj.uz

Submission #399456

# Submission time Handle Problem Language Result Execution time Memory
399456 2021-05-05T20:36:15 Z ljuba Werewolf (IOI18_werewolf) C++17
100 / 100
 779 ms 131784 KB 
#include <bits/stdc++.h>
#include "werewolf.h"

using namespace std;

const int mxN = 2e5 + 12;
const int mxN2 = 6e5 + 12;

vector<int> adj[mxN];

struct DSU {
    int dsu[mxN2];
    int in[mxN2], out[mxN2];
    vector<int> adj[mxN2];
    vector<int> order;
    int n;
    int timer;

    DSU(int _n) : n(_n) {
        iota(dsu, dsu+mxN2, 0);
        order.push_back(mxN2);
        timer = 0;
    }

    int findSet(int u) {
        if(u == dsu[u])
            return u;
        return dsu[u] = findSet(dsu[u]);
    }

    void unite(int u, int v) {
        u = findSet(u);
        v = findSet(v);
        if(u == v)
            return;
        dsu[u] = dsu[v] = n;
        adj[n].push_back(u);
        adj[n].push_back(v);
        ++n;
    }

    void dfs(int s) {
        order.push_back(s);
        in[s] = ++timer;
        for(auto e : adj[s]) {
            dfs(e);
        }
        out[s] = timer;
    }
};

int ft[mxN2];

void update(int i, int x) {
    for(; i < mxN2; i += i&-i)
        ft[i] += x;
}

int query(int i) {
    int r = 0;
    for(; i; i -= i&-i)
        r += ft[i];
    return r;
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {

    int n = N;
    int m = (int)X.size();
    int q = (int)S.size();

    for(int i = 0; i < m; ++i) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }

    vector<int> queryL[mxN];
    vector<int> queryR[mxN];

    for(int i = 0; i < q; ++i) {
        queryL[L[i]].push_back(i);
        queryR[R[i]].push_back(i);
    }

    DSU levi(n);
    for(int i = n-1; ~i; --i) {
        for(auto e : adj[i]) {
            if(e > i)
                levi.unite(i, e);
        }

        for(auto z : queryL[i]) {
            S[z] = levi.findSet(S[z]);
        }
    }

    //for(auto z : S)
        //cerr << z << " ";
    //cerr << endl;
    //cerr << "----------" << endl;

    //cerr << levi.n-1 << " " << levi.findSet(n-1) << endl;
    levi.dfs(levi.n-1);

    DSU desni(n);

    for(int i = 0; i < n; ++i) {
        for(auto e : adj[i]) {
            if(i > e)
                desni.unite(i, e);
        }

        for(auto z : queryR[i]) {
            E[z] = desni.findSet(E[z]);
        }
    }

    //cerr << desni.n-1 << " " << desni.findSet(n-1) << endl;
    desni.dfs(desni.n-1);
    //for(auto z : levi.order)
        //cerr << z << " ";
    //cerr << endl;
    //for(auto z : desni.order)
        //cerr << z << " ";
    //cerr << endl;
    //cerr << "----------" << endl;

    vector<pair<int, int>> doga[mxN2];

    //verovatno ti je ovaj deo los

    for(int i = 0; i < q; ++i) {
        //cerr << levi.in[S[i]] - 1 << " " << levi.out[S[i]] << endl;
        doga[levi.in[S[i]] - 1].push_back({i, -1});
        doga[levi.out[S[i]]].push_back({i, 1});
    }

    //for(int i = 0; i < 50; ++i)
        //cerr << doga[i].size() << " ";
    //cerr << endl;

    vector<int> ans(q);

    //assert((int)levi.order.size() == levi.n);

    for(int i = 0; i < (int)levi.order.size(); ++i) {
        if(levi.order[i] < n)
            update(desni.in[levi.order[i]], 1);
        //cerr << "Vel: " << doga[i].size() << endl;
        for(auto z : doga[i]) {
            int izraz = query(desni.out[E[z.first]]) - query(desni.in[E[z.first]]-1);
            //cerr << "izraz" << endl;
            ans[z.first] += izraz * z.second;
            //cerr << izraz << endl;
        }
    }

    //cerr << "bu" << endl;

    for(auto &z : ans)
        z = (z > 0);

    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 61380 KB Output is correct
2 Correct 36 ms 61416 KB Output is correct
3 Correct 33 ms 61456 KB Output is correct
4 Correct 32 ms 61340 KB Output is correct
5 Correct 33 ms 61324 KB Output is correct
6 Correct 33 ms 61388 KB Output is correct
7 Correct 33 ms 61380 KB Output is correct
8 Correct 33 ms 61332 KB Output is correct
9 Correct 33 ms 61444 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 61380 KB Output is correct
2 Correct 36 ms 61416 KB Output is correct
3 Correct 33 ms 61456 KB Output is correct
4 Correct 32 ms 61340 KB Output is correct
5 Correct 33 ms 61324 KB Output is correct
6 Correct 33 ms 61388 KB Output is correct
7 Correct 33 ms 61380 KB Output is correct
8 Correct 33 ms 61332 KB Output is correct
9 Correct 33 ms 61444 KB Output is correct
10 Correct 39 ms 62276 KB Output is correct
11 Correct 41 ms 62408 KB Output is correct
12 Correct 39 ms 62228 KB Output is correct
13 Correct 39 ms 62444 KB Output is correct
14 Correct 39 ms 62392 KB Output is correct
15 Correct 40 ms 62404 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 699 ms 122000 KB Output is correct
2 Correct 575 ms 125636 KB Output is correct
3 Correct 609 ms 122352 KB Output is correct
4 Correct 563 ms 120708 KB Output is correct
5 Correct 577 ms 121096 KB Output is correct
6 Correct 646 ms 121784 KB Output is correct
7 Correct 556 ms 118540 KB Output is correct
8 Correct 553 ms 125448 KB Output is correct
9 Correct 478 ms 120496 KB Output is correct
10 Correct 479 ms 119108 KB Output is correct
11 Correct 498 ms 119252 KB Output is correct
12 Correct 530 ms 119864 KB Output is correct
13 Correct 595 ms 125756 KB Output is correct
14 Correct 624 ms 125852 KB Output is correct
15 Correct 641 ms 125968 KB Output is correct
16 Correct 617 ms 125876 KB Output is correct
17 Correct 585 ms 118400 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 61380 KB Output is correct
2 Correct 36 ms 61416 KB Output is correct
3 Correct 33 ms 61456 KB Output is correct
4 Correct 32 ms 61340 KB Output is correct
5 Correct 33 ms 61324 KB Output is correct
6 Correct 33 ms 61388 KB Output is correct
7 Correct 33 ms 61380 KB Output is correct
8 Correct 33 ms 61332 KB Output is correct
9 Correct 33 ms 61444 KB Output is correct
10 Correct 39 ms 62276 KB Output is correct
11 Correct 41 ms 62408 KB Output is correct
12 Correct 39 ms 62228 KB Output is correct
13 Correct 39 ms 62444 KB Output is correct
14 Correct 39 ms 62392 KB Output is correct
15 Correct 40 ms 62404 KB Output is correct
16 Correct 699 ms 122000 KB Output is correct
17 Correct 575 ms 125636 KB Output is correct
18 Correct 609 ms 122352 KB Output is correct
19 Correct 563 ms 120708 KB Output is correct
20 Correct 577 ms 121096 KB Output is correct
21 Correct 646 ms 121784 KB Output is correct
22 Correct 556 ms 118540 KB Output is correct
23 Correct 553 ms 125448 KB Output is correct
24 Correct 478 ms 120496 KB Output is correct
25 Correct 479 ms 119108 KB Output is correct
26 Correct 498 ms 119252 KB Output is correct
27 Correct 530 ms 119864 KB Output is correct
28 Correct 595 ms 125756 KB Output is correct
29 Correct 624 ms 125852 KB Output is correct
30 Correct 641 ms 125968 KB Output is correct
31 Correct 617 ms 125876 KB Output is correct
32 Correct 585 ms 118400 KB Output is correct
33 Correct 750 ms 123384 KB Output is correct
34 Correct 331 ms 98544 KB Output is correct
35 Correct 778 ms 126828 KB Output is correct
36 Correct 779 ms 122764 KB Output is correct
37 Correct 722 ms 126008 KB Output is correct
38 Correct 720 ms 123452 KB Output is correct
39 Correct 690 ms 131784 KB Output is correct
40 Correct 683 ms 128056 KB Output is correct
41 Correct 617 ms 123920 KB Output is correct
42 Correct 555 ms 119992 KB Output is correct
43 Correct 720 ms 130028 KB Output is correct
44 Correct 657 ms 125212 KB Output is correct
45 Correct 543 ms 129340 KB Output is correct
46 Correct 550 ms 129080 KB Output is correct
47 Correct 601 ms 125948 KB Output is correct
48 Correct 593 ms 125776 KB Output is correct
49 Correct 584 ms 126040 KB Output is correct
50 Correct 585 ms 125896 KB Output is correct
51 Correct 636 ms 126424 KB Output is correct
52 Correct 646 ms 126372 KB Output is correct