oj.uz

Submission #476679

# Submission time Handle Problem Language Result Execution time Memory
476679 2021-09-28T06:23:15 Z cookiemonster04 Werewolf (IOI18_werewolf) C++17
100 / 100
 1128 ms 129536 KB 
#include<bits/stdc++.h>
#include<unordered_set>

using namespace std;
#define LL long long
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define f first
#define s second

vector<vector<int>> adj;

struct DSU {
	vector<int> par, size, top;
    bool topmax;
	DSU(int N, bool mx){
		par.resize(N); size.resize(N); top.resize(N);
	    for (int i = 0; i < N; ++i) {
            size[i] = 1;
	        par[i] = i;
            top[i] = i;
	    }
        topmax = mx;
	}
	int find(int node) {
	    if (par[node] != node) {
	    	par[node] = find(par[node]);
	    }
	    return par[node];
	}
	void merge(int A, int B) {
	    int rootA = find(A);
	    int rootB = find(B);
		if (rootA == rootB) return;
        top[rootA] = top[rootB] = topmax ? max(top[rootA], top[rootB]) : min(top[rootA], top[rootB]);
	    if (size[rootA] > size[rootB]) {
	        par[rootB] = rootA;
	        size[rootA] += size[rootB];
	    }
	    else {
	        par[rootA] = rootB;
	        size[rootB] += size[rootA];
	    }
	}
};

struct MST {
    vector<vector<int>> tree;
    vector<int> lBound, rBound;
    MST(vector<int> &input) {
        tree.resize(4*input.size()+1);
        lBound.resize(4*input.size()+1);
        rBound.resize(4*input.size()+1);
        build(0, 0, input.size()-1, input);
    }
    void build(int node, int L, int R, vector<int> &arr) {
        lBound[node] = L; rBound[node] = R;
        if (L == R) {
            tree[node].pb(arr[L]); return;
        }
        build(2*node+1, L, (L+R)/2, arr); build(2*node+2, (L+R)/2+1, R, arr);
        auto lptr = tree[2*node+1].begin(), rptr = tree[2*node+2].begin();
        auto lend = tree[2*node+1].end(), rend = tree[2*node+2].end();
        while(lptr != lend && rptr != rend) {
            if (*lptr < *rptr) {
                tree[node].pb(*lptr);
                lptr++;
            } else {
                tree[node].pb(*rptr);
                rptr++;
            }
        }
        while(lptr != lend) {
            tree[node].pb(*lptr);
            lptr++;
        }
        while(rptr != rend) {
            tree[node].pb(*rptr);
            rptr++;
        }
    }
    bool contains(int node, int dL, int dR) {
        if (tree[node].back() < dL || tree[node].front() > dR) return false;
        int min = -1, max = tree[node].size()-1;
        while(max-min > 1) {
            int mid = (min+max) >> 1;
            if (tree[node][mid] >= dL) {
                max = mid;
            } else {
                min = mid;
            }
        }
        if (tree[node][max] <= dR) return true;
        return false;
    }
    bool query(int node, int qL, int qR, int dL, int dR) {
        if (qR < lBound[node] || qL > rBound[node]) return false;
        if (qL <= lBound[node] && rBound[node] <= qR) {
            return contains(node, dL, dR);
        }
        return query(2*node+1, qL, qR, dL, dR) || query(2*node+2, qL, qR, dL, dR);
    }
};


vector<int> hstart, hend, wstart, wend;

int hpar[19][200005], wpar[19][200005];

vector<int> input;

void hdfs(int c, int p, vector<int> &heuler, vector<vector<int>> &hadj) {
    hpar[0][c] = p;
    hstart[c] = heuler.size();
    heuler.pb(c);
    for (int to : hadj[c]) {
        hdfs(to, c, heuler, hadj);
    }
    hend[c] = heuler.size()-1;
}

int cwidx = 0;
void wdfs(int c, int p, vector<int> &widx, vector<vector<int>> &wadj) {
    wpar[0][c] = p;
    widx[c] = cwidx;
    wstart[c] = cwidx;
    cwidx++;
    for (int to : wadj[c]) {
        wdfs(to, c, widx, wadj);
    }
    wend[c] = cwidx-1;
}

void input_gen(int N, vector<int> &X, vector<int> &Y, vector<int> &S, vector<int> &E, vector<int> &L, vector<int> &R) {
    vector<int> heuler, widx;
    vector<vector<int>> hadj, wadj;
    adj.resize(N+5);
    for (int i = 0; i < X.size(); i++) {
        adj[X[i]].pb(Y[i]); adj[Y[i]].pb(X[i]);
    }
    hadj.resize(N+5); wadj.resize(N+5);
    widx.resize(N+5);
    DSU h(N+5, false), w(N+5, true);

    for (int i = N-1; i >= 0; i--) {
        unordered_set<int> added;
        for (int to : adj[i]) {
            if (to > i) {
                int root = h.find(to);
                int rtop = h.top[root];
                if (added.find(rtop) == added.end()) {
                    added.insert(rtop);
                    hadj[i].pb(rtop);
                }
            }
        }
        for (int val : added) h.merge(i, val);
    }
    for (int i = 0; i < N; i++) {
        unordered_set<int> added;
        for (int to : adj[i]) {
            if (to < i) {
                int root = w.find(to);
                int rtop = w.top[root];
                if (added.find(rtop) == added.end()) {
                    added.insert(rtop);
                    wadj[i].pb(rtop);
                }
            }
        }
        for (int val : added) w.merge(i, val);
    }

    hdfs(0, -1, heuler, hadj); wdfs(N-1, -1, widx, wadj);

    input.resize(N);
    for (int i = 0; i < N; i++) {
        input[i] = widx[heuler[i]];
    }
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
    ios::sync_with_stdio(0);
    hstart.resize(N+5); hend.resize(N+5);
    wstart.resize(N+5); wend.resize(N+5);

    input_gen(N, X, Y, S, E, L, R);

    MST tree(input);

    for (int i = 1; i <= 18; i++) {
        for (int j = 0; j < N; j++) {
            if (hpar[i-1][j] == -1) hpar[i][j] = -1;
            else hpar[i][j] = hpar[i-1][hpar[i-1][j]];
            if (wpar[i-1][j] == -1) wpar[i][j] = -1;
            else wpar[i][j] = wpar[i-1][wpar[i-1][j]];
        }
    }
    vector<int> ret;
    for (int q = 0; q < S.size(); q++) {
        if (S[q] < L[q] || E[q] > R[q]) {
            cout << 0 << endl; continue;
        }
        for (int i = 18; i >= 0; i--) {
            if (hpar[i][S[q]] >= L[q]) {
                S[q] = hpar[i][S[q]];
            }
            if (wpar[i][E[q]] != -1 && wpar[i][E[q]] <= R[q]) {
                E[q] = wpar[i][E[q]];
            }
        }
        ret.pb(tree.query(0, hstart[S[q]], hend[S[q]], wstart[E[q]], wend[E[q]]));
    }
    return ret;
}

// int main() {
//     int N, M, Q;
//     cin >> N >> M >> Q;
//     vector<int> X, Y, S, E, L, R;
//     for (int i = 0; i < M; i++) {
//         int a, b;
//         cin >> a >> b;
//         X.pb(a); Y.pb(b);
//     }
//     for (int i = 0; i < Q; i++) {
//         int s, e, l, r;
//         cin >> s >> e >> l >> r;
//         S.pb(s); E.pb(e); L.pb(l); R.pb(r);
//     }
//     vector<int> ret = check_validity(N, X, Y, S, E, L, R);
//     for (int i = 0; i < ret.size(); i++) {
//         cout << ret[i] << endl;
//     }
// }

Compilation message

werewolf.cpp: In function 'void input_gen(int, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
werewolf.cpp:139:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     for (int i = 0; i < X.size(); i++) {
      |                     ~~^~~~~~~~~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:201:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |     for (int q = 0; q < S.size(); q++) {
      |                     ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 8 ms 2252 KB Output is correct
11 Correct 8 ms 2124 KB Output is correct
12 Correct 8 ms 2124 KB Output is correct
13 Correct 11 ms 2380 KB Output is correct
14 Correct 9 ms 2292 KB Output is correct
15 Correct 10 ms 2284 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 963 ms 107972 KB Output is correct
2 Correct 898 ms 121012 KB Output is correct
3 Correct 820 ms 117880 KB Output is correct
4 Correct 843 ms 116688 KB Output is correct
5 Correct 858 ms 116636 KB Output is correct
6 Correct 896 ms 116364 KB Output is correct
7 Correct 823 ms 116412 KB Output is correct
8 Correct 817 ms 120956 KB Output is correct
9 Correct 618 ms 117884 KB Output is correct
10 Correct 646 ms 116864 KB Output is correct
11 Correct 658 ms 116684 KB Output is correct
12 Correct 593 ms 116408 KB Output is correct
13 Correct 976 ms 122688 KB Output is correct
14 Correct 983 ms 122812 KB Output is correct
15 Correct 984 ms 122804 KB Output is correct
16 Correct 963 ms 122748 KB Output is correct
17 Correct 761 ms 116412 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 8 ms 2252 KB Output is correct
11 Correct 8 ms 2124 KB Output is correct
12 Correct 8 ms 2124 KB Output is correct
13 Correct 11 ms 2380 KB Output is correct
14 Correct 9 ms 2292 KB Output is correct
15 Correct 10 ms 2284 KB Output is correct
16 Correct 963 ms 107972 KB Output is correct
17 Correct 898 ms 121012 KB Output is correct
18 Correct 820 ms 117880 KB Output is correct
19 Correct 843 ms 116688 KB Output is correct
20 Correct 858 ms 116636 KB Output is correct
21 Correct 896 ms 116364 KB Output is correct
22 Correct 823 ms 116412 KB Output is correct
23 Correct 817 ms 120956 KB Output is correct
24 Correct 618 ms 117884 KB Output is correct
25 Correct 646 ms 116864 KB Output is correct
26 Correct 658 ms 116684 KB Output is correct
27 Correct 593 ms 116408 KB Output is correct
28 Correct 976 ms 122688 KB Output is correct
29 Correct 983 ms 122812 KB Output is correct
30 Correct 984 ms 122804 KB Output is correct
31 Correct 963 ms 122748 KB Output is correct
32 Correct 761 ms 116412 KB Output is correct
33 Correct 1071 ms 117856 KB Output is correct
34 Correct 314 ms 32700 KB Output is correct
35 Correct 1117 ms 121044 KB Output is correct
36 Correct 993 ms 117148 KB Output is correct
37 Correct 1122 ms 119932 KB Output is correct
38 Correct 1082 ms 118072 KB Output is correct
39 Correct 949 ms 129100 KB Output is correct
40 Correct 971 ms 126796 KB Output is correct
41 Correct 878 ms 119376 KB Output is correct
42 Correct 697 ms 117388 KB Output is correct
43 Correct 1012 ms 125524 KB Output is correct
44 Correct 1128 ms 120008 KB Output is correct
45 Correct 777 ms 129536 KB Output is correct
46 Correct 795 ms 129200 KB Output is correct
47 Correct 1028 ms 122972 KB Output is correct
48 Correct 968 ms 122688 KB Output is correct
49 Correct 1039 ms 122908 KB Output is correct
50 Correct 987 ms 122892 KB Output is correct
51 Correct 858 ms 127016 KB Output is correct
52 Correct 833 ms 127128 KB Output is correct