oj.uz

Submission #434611

# Submission time Handle Problem Language Result Execution time Memory
434611 2021-06-21T13:05:17 Z dxz05 Werewolf (IOI18_werewolf) C++14
34 / 100
 1634 ms 90720 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];


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]);
    }

    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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 19148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 19148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1297 ms 90268 KB Output is correct
2 Correct 1439 ms 90400 KB Output is correct
3 Correct 1568 ms 90564 KB Output is correct
4 Correct 1546 ms 90648 KB Output is correct
5 Correct 1634 ms 90540 KB Output is correct
6 Correct 1502 ms 90528 KB Output is correct
7 Correct 1382 ms 90212 KB Output is correct
8 Correct 1406 ms 90492 KB Output is correct
9 Correct 834 ms 88556 KB Output is correct
10 Correct 830 ms 89208 KB Output is correct
11 Correct 971 ms 90232 KB Output is correct
12 Correct 732 ms 90232 KB Output is correct
13 Correct 1505 ms 90624 KB Output is correct
14 Correct 1555 ms 90664 KB Output is correct
15 Correct 1480 ms 90720 KB Output is correct
16 Correct 1573 ms 90512 KB Output is correct
17 Correct 1323 ms 90480 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 19148 KB Output isn't correct
2 Halted 0 ms 0 KB -