oj.uz

Submission #447551

# Submission time Handle Problem Language Result Execution time Memory
447551 2021-07-26T17:50:07 Z blue Werewolf (IOI18_werewolf) C++17
100 / 100
 1398 ms 173164 KB 
#include "werewolf.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxN = 200000;
vector<int> edge[maxN];
vector<int> col(maxN);
vector<int> col_list[maxN];
vector<int> minV(maxN); //min value in color i.
vector<int> child1[maxN];
vector<int> order1;
vector<int> pos1(maxN);
vector<int> subtree1(maxN, 1);
int anc1[maxN][20];
vector<int> depth1(maxN);
void dfs1(int u) {
    // cerr << "dfs1 " << u << '\n';
    pos1[u] = int(order1.size());
    order1.push_back(u);
    for(int v: child1[u]) {
        anc1[v][0] = u;
        for(int e = 1; e < 20; e++)
            anc1[v][e] = anc1[ anc1[v][e-1] ][e-1];
        depth1[v] = depth1[u] + 1;
        dfs1(v);
        subtree1[u] += subtree1[v];
    }
}
vector<int> maxV(maxN);
vector<int> child2[maxN];
vector<int> order2;
vector<int> pos2(maxN);
vector<int> subtree2(maxN, 1);
int anc2[maxN][20];
vector<int> depth2(maxN);
void dfs2(int u) {
    pos2[u] = int(order2.size());
    order2.push_back(u);
    for(int v: child2[u]) {
        anc2[v][0] = u;
        for(int e = 1; e < 20; e++)
            anc2[v][e] = anc2[ anc2[v][e-1] ][e-1];
        depth2[v] = depth2[u] + 1;
        dfs2(v);
        subtree2[u] += subtree2[v];
    }
}
vector<int> init(maxN);
struct segtree {
    int l;
    int r;
    vector<int> V;
    segtree* left = NULL;
    segtree* right = NULL;
    segtree() {
        ;
    }
    segtree(int L, int R) {
        l = L;
        r = R;
        if(l == r) {
            V.push_back(init[l]);
        }
        else {
            int m = (l+r)/2;
            left = new segtree(l, m);
            right = new segtree(m+1, r);
            for(int v: left->V) V.push_back(v);
            for(int v: right->V) V.push_back(v);
            sort(V.begin(), V.end());
        }
    }
    bool query(int L, int R, int X, int Y) {
        if(R < l || r < L) return 0;
        else if(L <= l && r <= R) {
            int s = -1;
            for(int e = 19; e >= 0; e--) {
                if(s + (1 << e) >= V.size()) continue;
                if(V[s + (1 << e)] <= Y)
                    s += (1 << e);
            }
            if(s == -1) return 0;
            return (V[s] >= X);
        }
        else return left->query(L, R, X, Y) || right->query(L, R, X, Y);
    }
};
segtree T;
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R)
{
    int M = X.size();
    for(int j = 0; j < M; j++) {
        edge[X[j]].push_back(Y[j]);
        edge[Y[j]].push_back(X[j]);
    }
    for(int e = 0; e < 20; e++) {
        anc1[0][e] = 0;
        anc2[N-1][e] = N-1;
    }
    depth1[0] = 0;
    depth2[N-1] = 0;
    for(int i = 0; i < N; i++)  {
        col_list[i].push_back(i);
        col[i] = minV[i] = i;
    }
    for(int u = N-1; u >= 0; u--) {
        for(int v: edge[u])  {
            if(v < u) continue;
            if(col[v] == col[u]) continue;
            child1[u].push_back(minV[col[v]]);
            int U = u, V = v;
            if(col_list[col[U]].size() < col_list[col[V]].size())
                swap(U, V);
            int colV = col[V];
            for(int x: col_list[colV])  {
                col[x] = col[U];
                col_list[col[U]].push_back(x);
            }
            minV[col[U]] = u;
        }
    }
    dfs1(0);
    for(int i = 0; i < N; i++) {
        col_list[i].clear();
        col_list[i].push_back(i);
        col[i] = maxV[i] = i;
    }
    for(int u = 0; u < N; u++) {
        for(int v: edge[u]) {
            if(v > u) continue;
            if(col[v] == col[u]) continue;
            child2[u].push_back(maxV[col[v]]);
            int U = u, V = v;
            if(col_list[col[U]].size() < col_list[col[V]].size())
                swap(U, V);
            int colV = col[V];
            for(int x: col_list[colV])  {
                col[x] = col[U];
                col_list[col[U]].push_back(x);
            }
            maxV[col[U]] = u;
        }
    }
    dfs2(N-1);
    for(int i = 0; i < N; i++) 
      init[ pos1[i] ] = pos2[i];
    T = segtree(0, N-1);
    int Q = S.size();
    vector<int> res(Q);
    for(int i = 0; i < Q; i++) {
        int s = S[i], e = E[i], l = L[i], r = R[i];
        for(int x = 19; x >= 0; x--){
            if(anc1[s][x] >= l)
                s = anc1[s][x];
        }
        for(int x = 19; x >= 0; x--) {
            if(anc2[e][x] <= r)
                e = anc2[e][x];
        }
        res[i] = T.query(pos1[s], pos1[s] + subtree1[s] - 1, pos2[e], pos2[e] + subtree2[e] - 1);
    }
    return res;
}

Compilation message

werewolf.cpp: In member function 'bool segtree::query(int, int, int, int)':
werewolf.cpp:79:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |                 if(s + (1 << e) >= V.size()) continue;
      |                    ~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26956 KB Output is correct
2 Correct 15 ms 26988 KB Output is correct
3 Correct 14 ms 26912 KB Output is correct
4 Correct 14 ms 26956 KB Output is correct
5 Correct 14 ms 26916 KB Output is correct
6 Correct 15 ms 26908 KB Output is correct
7 Correct 15 ms 26964 KB Output is correct
8 Correct 15 ms 26972 KB Output is correct
9 Correct 16 ms 27004 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26956 KB Output is correct
2 Correct 15 ms 26988 KB Output is correct
3 Correct 14 ms 26912 KB Output is correct
4 Correct 14 ms 26956 KB Output is correct
5 Correct 14 ms 26916 KB Output is correct
6 Correct 15 ms 26908 KB Output is correct
7 Correct 15 ms 26964 KB Output is correct
8 Correct 15 ms 26972 KB Output is correct
9 Correct 16 ms 27004 KB Output is correct
10 Correct 23 ms 28876 KB Output is correct
11 Correct 23 ms 28756 KB Output is correct
12 Correct 23 ms 28780 KB Output is correct
13 Correct 22 ms 29004 KB Output is correct
14 Correct 26 ms 29056 KB Output is correct
15 Correct 25 ms 28876 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1147 ms 163132 KB Output is correct
2 Correct 1004 ms 160660 KB Output is correct
3 Correct 889 ms 158724 KB Output is correct
4 Correct 949 ms 159560 KB Output is correct
5 Correct 955 ms 159968 KB Output is correct
6 Correct 1079 ms 161040 KB Output is correct
7 Correct 1151 ms 163424 KB Output is correct
8 Correct 920 ms 160704 KB Output is correct
9 Correct 756 ms 158392 KB Output is correct
10 Correct 822 ms 159604 KB Output is correct
11 Correct 865 ms 159944 KB Output is correct
12 Correct 859 ms 160952 KB Output is correct
13 Correct 1218 ms 166544 KB Output is correct
14 Correct 1160 ms 166432 KB Output is correct
15 Correct 1187 ms 166452 KB Output is correct
16 Correct 1194 ms 166460 KB Output is correct
17 Correct 1139 ms 163408 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26956 KB Output is correct
2 Correct 15 ms 26988 KB Output is correct
3 Correct 14 ms 26912 KB Output is correct
4 Correct 14 ms 26956 KB Output is correct
5 Correct 14 ms 26916 KB Output is correct
6 Correct 15 ms 26908 KB Output is correct
7 Correct 15 ms 26964 KB Output is correct
8 Correct 15 ms 26972 KB Output is correct
9 Correct 16 ms 27004 KB Output is correct
10 Correct 23 ms 28876 KB Output is correct
11 Correct 23 ms 28756 KB Output is correct
12 Correct 23 ms 28780 KB Output is correct
13 Correct 22 ms 29004 KB Output is correct
14 Correct 26 ms 29056 KB Output is correct
15 Correct 25 ms 28876 KB Output is correct
16 Correct 1147 ms 163132 KB Output is correct
17 Correct 1004 ms 160660 KB Output is correct
18 Correct 889 ms 158724 KB Output is correct
19 Correct 949 ms 159560 KB Output is correct
20 Correct 955 ms 159968 KB Output is correct
21 Correct 1079 ms 161040 KB Output is correct
22 Correct 1151 ms 163424 KB Output is correct
23 Correct 920 ms 160704 KB Output is correct
24 Correct 756 ms 158392 KB Output is correct
25 Correct 822 ms 159604 KB Output is correct
26 Correct 865 ms 159944 KB Output is correct
27 Correct 859 ms 160952 KB Output is correct
28 Correct 1218 ms 166544 KB Output is correct
29 Correct 1160 ms 166432 KB Output is correct
30 Correct 1187 ms 166452 KB Output is correct
31 Correct 1194 ms 166460 KB Output is correct
32 Correct 1139 ms 163408 KB Output is correct
33 Correct 1303 ms 157580 KB Output is correct
34 Correct 335 ms 58556 KB Output is correct
35 Correct 1354 ms 159868 KB Output is correct
36 Correct 1279 ms 158308 KB Output is correct
37 Correct 1398 ms 158788 KB Output is correct
38 Correct 1279 ms 158592 KB Output is correct
39 Correct 1129 ms 173076 KB Output is correct
40 Correct 1341 ms 167388 KB Output is correct
41 Correct 1134 ms 158288 KB Output is correct
42 Correct 1006 ms 158292 KB Output is correct
43 Correct 1236 ms 165868 KB Output is correct
44 Correct 1245 ms 158820 KB Output is correct
45 Correct 892 ms 172640 KB Output is correct
46 Correct 904 ms 173164 KB Output is correct
47 Correct 1229 ms 166612 KB Output is correct
48 Correct 1131 ms 166444 KB Output is correct
49 Correct 1233 ms 166540 KB Output is correct
50 Correct 1190 ms 166576 KB Output is correct
51 Correct 1255 ms 167264 KB Output is correct
52 Correct 1282 ms 167408 KB Output is correct