oj.uz

Submission #988854

# Submission time Handle Problem Language Result Execution time Memory
988854 2024-05-26T13:22:32 Z Essa2006 Werewolf (IOI18_werewolf) C++14
0 / 100
 4000 ms 121792 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)

const int lg = 19, inf = 1e9;
int n, cur;
vector<vector<int>> A;
vector<array<int, 2>> P, Anc, L, R, Vis, Dsc, Fin;
vector<vector<array<int, 2>>> Up;

int find(int ind, int id) {
    if (P[ind][id] == ind) {
        return ind;
    }
    return P[ind][id] = find(P[ind][id], id);
}

array<int, 2> cnt;
void merge(int a, int b, int id) {
    int ga = find(a, id), gb = find(b, id);
    if (ga == gb) {
        return ;
    }

    Anc[cnt[id]][id] = cur;
    L[cnt[id]][id] = ga, R[cnt[id]][id] = gb;
    Up[ga][0][id] = Up[gb][0][id] = P[ga][id] = P[gb][id] = cnt[id]++;

    return;
}

array<int, 2> time_;
void build(int u, int id) {
    Dsc[u][id] = time_[id]++;
    Vis[u][id] = 1;


    if (Up[u][0][id] == -1) {
        for (int j = 0; j <= lg; j++) {
            Up[u][j][id] = u;
        }
    }
    else {
        for (int j = 1; j <= lg; j++) {
            Up[u][j][id] = Up[Up[u][j - 1][id]][j - 1][id];
        }
    }

    if (u >= n) {
        build(L[u][id], id);
        build(R[u][id], id);
    }

    Fin[u][id] = time_[id]++;
}

int lca(int u, int c, int id) {
    for (int j = lg; j >= 0; j--) {
        if (Anc[Up[u][j][id]][id] <= c) {
            u = Up[u][j][id];
        }
    }
    return u;
}

vector<int> check_validity(int nn, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> LL, vector<int> RR) {
    n = nn;
    cnt[0] = cnt[1] = n;
    A.resize(n), P.resize(2 * n), Anc.resize(2 * n, {inf, inf}), L.resize(2 * n), R.resize(2 * n), Vis.resize(2 * n), Dsc.resize(2 * n), Fin.resize(2 * n);
    Up.resize(2 * n, vector<array<int, 2>>(lg + 1, {-1, -1}));
    for (int i = 0; i < 2 * n; i++) {
        P[i][0] = P[i][1] = i;
    }


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

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < A[i].size(); j++) {
            if (A[i][j] < i) {
                cur = i;
                merge(i, A[i][j], 0);
            }
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < A[i].size(); j++) {
            if (A[i][j] > i) {
                cur =  n - 1 - i;
                merge(i, A[i][j], 1);
            }
        }
    }


    for (int j = 0; j < 2; j++) {
        for (int i = cnt[j] - 1; i >= 0; i--) {
            if (!Vis[i][j]) {
                build(i, j);
            }
        }
    }

    vector<int> Ans(LL.size());

    for (int i = 0; i < S.size(); i++) {
        int u = lca(S[i], RR[i], 0), v = lca(E[i], (n - 1) - LL[i], 1);
        if (u == cnt[0] - 1) {
            assert(RR[i] == n - 1);
        }
        if (v == cnt[1] - 1) {
            assert(LL[i] == 0);
        }
        for (int j = 0; j < n; j++) {
            if (Dsc[u][0] <= Dsc[j][0] && Fin[j][0] <= Fin[u][0]) {
                if (Dsc[v][1] <= Dsc[j][1] && Fin[j][1] <= Fin[v][1]) {
                    Ans[i] = 1;
                }
            }

        }
    }


    return Ans;


}

Compilation message

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:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int i = 0; i < X.size(); i++) {
      |                     ~~^~~~~~~~~~
werewolf.cpp:87:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for (int j = 0; j < A[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~
werewolf.cpp:95:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for (int j = 0; j < A[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~
werewolf.cpp:114:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for (int i = 0; i < S.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4053 ms 121792 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

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