oj.uz

Submission #439898

# Submission time Handle Problem Language Result Execution time Memory
439898 2021-07-01T06:57:56 Z dxz05 Werewolf (IOI18_werewolf) C++14
49 / 100
 1883 ms 98512 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 4e5 + 3e2;

#define MP make_pair
#define PII pair<int, int>

vector<int> g[MAXN];

bool used[MAXN];
int tin[MAXN];
vector<int> vec = {0};
void dfs(int v){
    used[v] = true;
    tin[v] = vec.size();
    vec.push_back(v);

    for (int u : g[v]){
        if (!used[u]){
            dfs(u);
        }
    }

}


PII t[MAXN][20];
int Log[MAXN];

PII combine(PII lf, PII rg){
    return MP(min(lf.first, rg.first), max(lf.second, rg.second));
}

void build(int n){
    Log[1] = 0;
    for (int i = 2; i <= n; i++) Log[i] = Log[i / 2] + 1;
    for (int i = 0; i < 20; i++){
        for (int j = 1; j <= n; j++){
            if (i == 0){
                t[j][i] = MP(vec[j], vec[j]);
            } else {
                if (j + (1 << (i - 1)) < MAXN) t[j][i] = combine(t[j][i - 1], t[j + (1 << (i - 1))][i - 1]);
            }
        }
    }
}

PII get(int l, int r){
    if (l > r) return MP(1e9, -1e9);
    if (l == r) return t[l][0];
    int x = Log[r - l + 1];
    PII res = combine(t[l][x], t[r - (1 << x) + 1][x]);

    return res;
}

PII get_positions(int X, int N, int L, int R){
    X = tin[X];
    int lf = X, rg = X;

    int l = 1, r = X;
    while (l <= r){
        int m = (l + r) >> 1;
        PII f = get(m, X);
        if (f.first >= L && f.second <= R){
            lf = m;
            r = m - 1;
        } else l = m + 1;
    }

    l = X, r = N;
    while (l <= r){
        int m = (l + r) >> 1;
        PII f = get(X, m);
        if (f.first >= L && f.second <= R){
            rg = m;
            l = m + 1;
        } else r = m - 1;
    }

    return MP(lf, rg);
}

int smaller[MAXN];

int fw[MAXN];
void add(int x, int y){
    while (x < MAXN){
        fw[x] += y;
        x += (-x & x);
    }
}

int get(int x){
    int ret = 0;
    while (x > 0){
        ret += fw[x];
        x -= (-x & x);
    }
    return ret;
}

vector<pair<PII, PII>> queries[MAXN];


void dfs2(int v, int l, int r, vector<bool> &used){
    used[v] = true;

    for (int u : g[v]){
        if (!used[u] && l <= u && u <= r){
            dfs2(u, l, r, used);
        }
    }
}

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 Q = S.size(), M = X.size();
    vector<int> A(Q, 0);

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

    if (N <= 3000 && M <= 6000 && Q <= 3000){
        for (int i = 0; i < Q; i++){
            vector<bool> used1(N, false), used2(N, false);
            dfs2(S[i], L[i], N - 1, used1);
            dfs2(E[i], 0, R[i], used2);

            for (int j = L[i]; j <= R[i]; j++){
                if (used1[j] && used2[j]) A[i] = 1;
            }

        }

        return A;
    }

    for (int i = 0; i < N; i++){
        if (g[i].size() == 1){
            dfs(i);
            break;
        }
    }

    build(N);

    for (int i = 0; i < Q; i++){
        PII fs = get_positions(S[i], N, L[i], N - 1), fe = get_positions(E[i], N, 0, R[i]);
        int l1 = fs.first, r1 = fs.second, l2 = fe.first, r2 = fe.second;

        //cout << "\t" << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << endl;

        int l = max(l1, l2), r = min(r1, r2);
        if (L[i]) queries[L[i] - 1].emplace_back(MP(i, 0), MP(l, r));
        queries[R[i]].emplace_back(MP(i, 1), MP(l, r));

    }

    //return A;

    for (int i = 0; i < N; i++){
        add(tin[i], 1);

        for (auto qu : queries[i]){
            int ind = qu.first.first, ty = qu.first.second, l = qu.second.first, r = qu.second.second;
           // cout << i << ' ' << l << ' ' << r << endl;
            int res = get(r) - get(l - 1);

            if (ty == 0) A[ind] -= res; else
                A[ind] += res;

        }

    }

    for (int i = 0; i < Q; i++) A[i] = A[i] > 0;


    return A;
}

/**
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4


6 5 1
2 0
0 1
3 5
1 3
5 4
1 4 0 4

*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 19020 KB Output is correct
2 Correct 13 ms 19108 KB Output is correct
3 Correct 15 ms 19124 KB Output is correct
4 Correct 15 ms 19072 KB Output is correct
5 Correct 17 ms 19008 KB Output is correct
6 Correct 14 ms 18996 KB Output is correct
7 Correct 14 ms 19100 KB Output is correct
8 Correct 15 ms 19020 KB Output is correct
9 Correct 15 ms 19020 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 19020 KB Output is correct
2 Correct 13 ms 19108 KB Output is correct
3 Correct 15 ms 19124 KB Output is correct
4 Correct 15 ms 19072 KB Output is correct
5 Correct 17 ms 19008 KB Output is correct
6 Correct 14 ms 18996 KB Output is correct
7 Correct 14 ms 19100 KB Output is correct
8 Correct 15 ms 19020 KB Output is correct
9 Correct 15 ms 19020 KB Output is correct
10 Correct 305 ms 19600 KB Output is correct
11 Correct 199 ms 19444 KB Output is correct
12 Correct 34 ms 19664 KB Output is correct
13 Correct 341 ms 19488 KB Output is correct
14 Correct 226 ms 19436 KB Output is correct
15 Correct 297 ms 19732 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1709 ms 98400 KB Output is correct
2 Correct 1648 ms 98292 KB Output is correct
3 Correct 1716 ms 98440 KB Output is correct
4 Correct 1644 ms 98300 KB Output is correct
5 Correct 1507 ms 98276 KB Output is correct
6 Correct 1820 ms 98316 KB Output is correct
7 Correct 1538 ms 97932 KB Output is correct
8 Correct 1415 ms 98316 KB Output is correct
9 Correct 849 ms 96156 KB Output is correct
10 Correct 824 ms 97020 KB Output is correct
11 Correct 1016 ms 97964 KB Output is correct
12 Correct 917 ms 98148 KB Output is correct
13 Correct 1809 ms 98324 KB Output is correct
14 Correct 1825 ms 98512 KB Output is correct
15 Correct 1881 ms 98312 KB Output is correct
16 Correct 1883 ms 98336 KB Output is correct
17 Correct 1580 ms 98304 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 19020 KB Output is correct
2 Correct 13 ms 19108 KB Output is correct
3 Correct 15 ms 19124 KB Output is correct
4 Correct 15 ms 19072 KB Output is correct
5 Correct 17 ms 19008 KB Output is correct
6 Correct 14 ms 18996 KB Output is correct
7 Correct 14 ms 19100 KB Output is correct
8 Correct 15 ms 19020 KB Output is correct
9 Correct 15 ms 19020 KB Output is correct
10 Correct 305 ms 19600 KB Output is correct
11 Correct 199 ms 19444 KB Output is correct
12 Correct 34 ms 19664 KB Output is correct
13 Correct 341 ms 19488 KB Output is correct
14 Correct 226 ms 19436 KB Output is correct
15 Correct 297 ms 19732 KB Output is correct
16 Correct 1709 ms 98400 KB Output is correct
17 Correct 1648 ms 98292 KB Output is correct
18 Correct 1716 ms 98440 KB Output is correct
19 Correct 1644 ms 98300 KB Output is correct
20 Correct 1507 ms 98276 KB Output is correct
21 Correct 1820 ms 98316 KB Output is correct
22 Correct 1538 ms 97932 KB Output is correct
23 Correct 1415 ms 98316 KB Output is correct
24 Correct 849 ms 96156 KB Output is correct
25 Correct 824 ms 97020 KB Output is correct
26 Correct 1016 ms 97964 KB Output is correct
27 Correct 917 ms 98148 KB Output is correct
28 Correct 1809 ms 98324 KB Output is correct
29 Correct 1825 ms 98512 KB Output is correct
30 Correct 1881 ms 98312 KB Output is correct
31 Correct 1883 ms 98336 KB Output is correct
32 Correct 1580 ms 98304 KB Output is correct
33 Incorrect 1583 ms 89200 KB Output isn't correct
34 Halted 0 ms 0 KB -