oj.uz

Submission #1077603

# Submission time Handle Problem Language Result Execution time Memory
1077603 2024-08-27T08:17:02 Z vjudge1 Werewolf (IOI18_werewolf) C++17
7 / 100
 4000 ms 93248 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;
using ull = unsigned long long;
const int BUCKET = 62;

struct DSU {
    vi e, mi, ma;
    DSU(int n) : e(n, -1), mi(n), ma(n) {
        iota(mi.begin(), mi.end(), 0);
        iota(ma.begin(), ma.end(), 0);
    }

    int repr(int u) {
        while(e[u] >= 0) u = e[u];
        return u;
    }

    bool join(int u, int v) {
        u = repr(u);
        v = repr(v);
        if(u == v) return false;
        if(e[u] >= e[v]) swap(u, v);
        mi[u] = min(mi[u], mi[v]);
        ma[u] = max(ma[u], ma[v]);
        e[u] += e[v];
        e[v] = u;
        return true;
    }

    bool same(int u, int v) {
        return repr(u) == repr(v);
    }

    ii seg(int u) { 
        u = repr(u);
        return make_pair(mi[u], ma[u]);
    }
};

struct BinLift {
    int n;
    vector<vi> A;
    BinLift(vi V) {
        n = int(V.size());
        A.push_back(V);
        for(int k = 1; (1 << k) <= n; ++k) {
            A.push_back(A.back());
            for(int i = 0; i < n; ++i)
                if(A[k - 1][i] < 0 || A[k - 1][i] >= n);
                else A[k][i] = A[k - 1][A[k - 1][i]];
        }
    }

    int lift(int u, int k) {
        return A[k][u];
    }
};


vi check_validity(int n, vi X, vi Y, vi S, vi E, vi L, vi R) {
    int q = (int)S.size(), m = (int)X.size();
    vector<vi> Lg(n);
    for(int i = 0; i < m; ++i) {
        Lg[X[i]].push_back(Y[i]);
        Lg[Y[i]].push_back(X[i]);
    }

    DSU St(n);
    vi GEpar(n, n), GSpar(n, -1);
    vector<vi> GE(n), GS(n);
    for(int i = 0; i < n; ++i) {
        for(auto it : Lg[i])
            if(it < i) {
                auto [mi, ma] = St.seg(it);
                if(St.join(it, i)) {
                    GE[i].push_back(ma);
                    GEpar[ma] = i;
                }
            }
    }

    DSU Dr(n);
    for(int i = n - 1; i >= 0; --i) {
        for(auto it : Lg[i]) {
            if(it > i) {
                auto [mi, ma] = Dr.seg(it);
                if(Dr.join(it, i)) {
                    GS[i].push_back(mi);
                    GSpar[mi] = i;
                }
            }
        }
    }

    vector<vi> G(n);
    for(int i = 0; i < n; ++i) {
        copy(GS[i].begin(), GS[i].end(), back_inserter(G[i]));
        for(auto it : GE[i])
            G[it].push_back(i);
    }

    BinLift BLS(GSpar), BLE(GEpar);

    auto reprS = [&](int u, int lim) {
        while(GSpar[u] >= lim) u = GSpar[u];
       // for(int k = int(BLS.A.size()) - 1; k >= 0; --k)
       //     if(BLS.lift(u, k) >= lim) u = BLS.lift(u, k);
        return u;
    };

    auto reprE = [&](int u, int lim) {
        while(GEpar[u] <= lim) u = GEpar[u];
      //  for(int k = int(BLE.A.size()) - 1; k >= 0; --k)
      //      if(BLE.lift(u, k) <= lim) u = BLE.lift(u, k);
        return u;
    };

    vi viz(n, 0);
    function<void(int)> dfs = [&](int u) {
        if(viz[u]) return;
        viz[u] = 1;
        for(auto it : G[u]) dfs(it);
    };
    for(int nr = 0; nr < q; ++nr) {
        S[nr] = reprS(S[nr], L[nr]);
        E[nr] = reprE(E[nr], R[nr]);
    }

    auto reachable = [&](int s, int t) {
        viz.assign(n, 0);
        dfs(s);
        return viz[t];
    };

    vi Re(q, 0);
    for(int i = 0; i < q; ++i) {
        Re[i] = reachable(S[i], E[i]);
    }

//    vector<ull> Val(n, 0);
//    for(int id = 0; id <= (q - 1) / BUCKET; ++id) {
//        int st = id * BUCKET, dr = st + BUCKET;
//        dr = min(dr, q);
//        for(int i = 0; i < n; ++i) Val[i] = 0;
//        for(int i = st; i < dr; ++i) {
//            Val[E[i]] |= (1ull << (i - st));
//        }
//        for(int i = n - 1; i >= 0; --i) {
//            for(auto it : G[i]) Val[i] |= Val[it];
//        }
//        for(int i = st; i < dr; ++i) {
//            Re[i] = !!(Val[S[i]] & (1ull << (i - st)));
//        }
//    }
    return Re;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Incorrect 61 ms 1704 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Incorrect 61 ms 1704 KB Output isn't correct
11 Halted 0 ms 0 KB -