oj.uz

Submission #200001

# Submission time Handle Problem Language Result Execution time Memory
200001 2020-02-04T17:24:18 Z jeff Werewolf (IOI18_werewolf) C++14
100 / 100
 962 ms 100064 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
 
int N, A[800000], id[400000], f[200000], l[2][2][400000], y, z;
pair<int, int> B[800000];
vector<int> adj[2][400000], rs;
vector<pair<int, int> > v;
vector<tuple<int, int, int, int, int> > qr;
 
inline int frt(int i) {return i == id[i] ? i : id[i] = frt(id[i]);}
 
inline void ufds(int t, int a, int b) {
    a = frt(a);
    b = frt(b);
    if (a == b) return;
    adj[t][a].push_back(y);
    adj[t][b].push_back(y);
    adj[t][y].push_back(a);
    adj[t][y].push_back(b);
    id[a] = id[b] = y++;
}
 
void it(int t, int i, int o) {
    l[t][0][i] = z;
    for (int j = 0; j < adj[t][i].size(); ++j) if (o != adj[t][i][j]) it(t, adj[t][i][j], i);
    if (i < N) {
        if (!t) f[z++] = i;
        else ++z;
    }
    l[t][1][i] = z - 1;
}
 
void init(int i, int a, int b) {
    A[i] = INT_MAX;
    B[i] = make_pair(a, b);
    if (a >= b) return;
    init(i * 2, a, (a + b) / 2);
    init(i * 2 + 1, (a + b) / 2 + 1, b);
}
 
int q(int i, int a, int b) {
    if (b < B[i].first || B[i].second < a) return INT_MAX;
    if (a <= B[i].first && B[i].second <= b) return A[i];
    return min(q(i * 2, a, b), q(i * 2 + 1, a, b));
}
 
void u(int i, int p, int v) {
    if (p < B[i].first || B[i].second < p) return;
    if (p <= B[i].first && B[i].second <= p) {A[i] = v; return;}
    u(i * 2, p, v);
    u(i * 2 + 1, p, v);
    A[i] = min(A[i * 2], A[i * 2 + 1]);
}
 
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;
    int M = X.size(), Q = S.size(), i, j;
    rs.assign(Q, 0);
    for (i = 0; i < Q; ++i) qr.emplace_back(R[i], L[i], E[i], S[i], i);
    for (i = 0; i < M; ++i) v.emplace_back(max(X[i], Y[i]), min(X[i], Y[i]));
    sort(v.begin(), v.end());
    sort(qr.begin(), qr.end());
    iota(id, id + N * 2 - 1, 0);
    y = N;
    for (i = j = 0; i < M; ++i) {
        while (j < Q && get<0>(qr[j]) < v[i].first) get<2>(qr[j]) = frt(get<2>(qr[j])), swap(get<0>(qr[j]), get<1>(qr[j])), ++j;
        ufds(0, v[i].first, v[i].second);
        swap(v[i].first, v[i].second);
    }
    while (j < Q) get<3>(qr[j]) = frt(get<3>(qr[j])), swap(get<0>(qr[j]), get<1>(qr[j])), ++j;
    sort(v.begin(), v.end());
    sort(qr.begin(), qr.end());
    iota(id, id + N * 2 - 1, 0);
    y = N;
    for (i = M - 1, j = Q - 1; i > -1; --i) {
        while (j > -1 && get<0>(qr[j]) > v[i].first) get<3>(qr[j]) = frt(get<3>(qr[j])), --j;
        ufds(1, v[i].first, v[i].second);
    }
    while (j > -1) get<2>(qr[j]) = frt(get<2>(qr[j])), --j;
    it(0, N * 2 - 2, -1);
    z = 0;
    it(1, N * 2 - 2, -1);
    for (i = 0; i < Q; ++i) get<0>(qr[i]) = l[0][0][get<2>(qr[i])], get<1>(qr[i]) = l[0][1][get<2>(qr[i])];
    sort(qr.begin(), qr.end());
    init(1, 0, N - 1);
    for (i = Q - 1, j = N - 1; i > -1; --i) {
        while (j >= get<0>(qr[i])) u(1, l[1][0][f[j]], j), --j;
        rs[get<4>(qr[i])] = q(1, l[1][0][get<3>(qr[i])], l[1][1][get<3>(qr[i])]) <= get<1>(qr[i]);
    }
    return rs;
}

Compilation message

werewolf.cpp: In function 'void it(int, int, int)':
werewolf.cpp:26:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[t][i].size(); ++j) if (o != adj[t][i][j]) it(t, adj[t][i][j], i);
                     ~~^~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19192 KB Output is correct
2 Correct 21 ms 19192 KB Output is correct
3 Correct 18 ms 19192 KB Output is correct
4 Correct 22 ms 19196 KB Output is correct
5 Correct 18 ms 19192 KB Output is correct
6 Correct 19 ms 19192 KB Output is correct
7 Correct 18 ms 19192 KB Output is correct
8 Correct 18 ms 19192 KB Output is correct
9 Correct 17 ms 19192 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19192 KB Output is correct
2 Correct 21 ms 19192 KB Output is correct
3 Correct 18 ms 19192 KB Output is correct
4 Correct 22 ms 19196 KB Output is correct
5 Correct 18 ms 19192 KB Output is correct
6 Correct 19 ms 19192 KB Output is correct
7 Correct 18 ms 19192 KB Output is correct
8 Correct 18 ms 19192 KB Output is correct
9 Correct 17 ms 19192 KB Output is correct
10 Correct 31 ms 20344 KB Output is correct
11 Correct 26 ms 20216 KB Output is correct
12 Correct 27 ms 20088 KB Output is correct
13 Correct 26 ms 20344 KB Output is correct
14 Correct 26 ms 20344 KB Output is correct
15 Correct 29 ms 20344 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 955 ms 83896 KB Output is correct
2 Correct 691 ms 91744 KB Output is correct
3 Correct 714 ms 86880 KB Output is correct
4 Correct 723 ms 84572 KB Output is correct
5 Correct 728 ms 84320 KB Output is correct
6 Correct 861 ms 83936 KB Output is correct
7 Correct 876 ms 83932 KB Output is correct
8 Correct 674 ms 91872 KB Output is correct
9 Correct 631 ms 86880 KB Output is correct
10 Correct 697 ms 84440 KB Output is correct
11 Correct 714 ms 84324 KB Output is correct
12 Correct 746 ms 84060 KB Output is correct
13 Correct 668 ms 91872 KB Output is correct
14 Correct 655 ms 91744 KB Output is correct
15 Correct 645 ms 91684 KB Output is correct
16 Correct 661 ms 91740 KB Output is correct
17 Correct 908 ms 84080 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19192 KB Output is correct
2 Correct 21 ms 19192 KB Output is correct
3 Correct 18 ms 19192 KB Output is correct
4 Correct 22 ms 19196 KB Output is correct
5 Correct 18 ms 19192 KB Output is correct
6 Correct 19 ms 19192 KB Output is correct
7 Correct 18 ms 19192 KB Output is correct
8 Correct 18 ms 19192 KB Output is correct
9 Correct 17 ms 19192 KB Output is correct
10 Correct 31 ms 20344 KB Output is correct
11 Correct 26 ms 20216 KB Output is correct
12 Correct 27 ms 20088 KB Output is correct
13 Correct 26 ms 20344 KB Output is correct
14 Correct 26 ms 20344 KB Output is correct
15 Correct 29 ms 20344 KB Output is correct
16 Correct 955 ms 83896 KB Output is correct
17 Correct 691 ms 91744 KB Output is correct
18 Correct 714 ms 86880 KB Output is correct
19 Correct 723 ms 84572 KB Output is correct
20 Correct 728 ms 84320 KB Output is correct
21 Correct 861 ms 83936 KB Output is correct
22 Correct 876 ms 83932 KB Output is correct
23 Correct 674 ms 91872 KB Output is correct
24 Correct 631 ms 86880 KB Output is correct
25 Correct 697 ms 84440 KB Output is correct
26 Correct 714 ms 84324 KB Output is correct
27 Correct 746 ms 84060 KB Output is correct
28 Correct 668 ms 91872 KB Output is correct
29 Correct 655 ms 91744 KB Output is correct
30 Correct 645 ms 91684 KB Output is correct
31 Correct 661 ms 91740 KB Output is correct
32 Correct 908 ms 84080 KB Output is correct
33 Correct 962 ms 85980 KB Output is correct
34 Correct 519 ms 55652 KB Output is correct
35 Correct 924 ms 91236 KB Output is correct
36 Correct 921 ms 85236 KB Output is correct
37 Correct 905 ms 89784 KB Output is correct
38 Correct 931 ms 86208 KB Output is correct
39 Correct 868 ms 99540 KB Output is correct
40 Correct 937 ms 95588 KB Output is correct
41 Correct 861 ms 88784 KB Output is correct
42 Correct 828 ms 85316 KB Output is correct
43 Correct 910 ms 96240 KB Output is correct
44 Correct 891 ms 89824 KB Output is correct
45 Correct 796 ms 100064 KB Output is correct
46 Correct 807 ms 99604 KB Output is correct
47 Correct 694 ms 91872 KB Output is correct
48 Correct 667 ms 91872 KB Output is correct
49 Correct 667 ms 92000 KB Output is correct
50 Correct 680 ms 91868 KB Output is correct
51 Correct 907 ms 96072 KB Output is correct
52 Correct 898 ms 96096 KB Output is correct