oj.uz

Submission #991466

# Submission time Handle Problem Language Result Execution time Memory
991466 2024-06-02T09:38:43 Z sleepntsheep September (APIO24_september) C++17
0 / 100
 5 ms 10588 KB 
#pragma GCC optimize("O2,unroll-loops")
#include "september.h"

#include <string>
#include <cstdio>
#include <array>
#include <vector>
#include <algorithm>

struct max_segtree { std::vector<int> st; int n; max_segtree(int n) : st(n * 2), n(n) {} void pul(int i) { st[i] = std::max(st[i << 1], st[i << 1 | 1]); } int query(int l, int r) { int z = 0; for (l += n, r += n + 1; l < r; l /= 2, r /= 2) { if (l & 1) z = std::max(z, st[l++]); if (r & 1) z = std::max(st[--r], z); } return z; } void assign(int p, int k) { for (st[p += n] = k; p /= 2; ) pul(p); } };

const int NN = 100000;
const int MM = 5;

std::vector<int> g[NN];

int M, tin[NN], tout[NN], timer, pos[MM][NN];

using Lena = std::array<int, 5>;

void add_(Lena &a, const Lena &b) {
    int i;
    for (i = 0; i < M; ++i)
        a[i] = std::max(a[i], b[i]);
}

Lena add(Lena a, const Lena &b) {
    add_(a, b);
    return a;
}

void dfs(int u) {
    tin[u] = timer++;
    for (auto v : g[u])
        dfs(v);
    tout[u] = timer - 1;
}

struct lena_segtree {
    std::vector<Lena> st;
    int n;

    lena_segtree(int n) : st(n * 2), n(n) {}

    void pul(int i) { st[i] = add(st[i << 1], st[i << 1 | 1]); }

    Lena query(int l, int r) { Lena z {}; for (l += n, r += n + 1; l < r; l /= 2, r /= 2) { if (l & 1) add_(z, st[l++]); if (r & 1) add_(z, st[--r]); } return z; }

    void update(int p, int q, int k) { p += n; st[p][q] = std::max(st[p][q], k); for (; p /= 2; ) pul(p); }
    void update2(int p, const Lena &x) { add_(st[p += n], x); for (; p /= 2; ) pul(p); }
};

int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
    int i, j;

    ::M = M;

    for (i = 0; i < N; ++i)
        g[i].clear();
    timer = 0;

    for (i = 0; i < M; ++i)
        for (j = 0; j < N - 1; ++j)
            pos[i][S[i][j]] = j;

    for (i = 1; i < N; ++i)
        g[F[i]].push_back(i);

    dfs(0);

    std::vector<lena_segtree> tb;
    std::vector<Lena> tc(N);
    lena_segtree ta(N);

    auto Put = [&](int u, Lena x) {
        add_(x, tc[u]);
        for (int j = 0; j < M; ++j)
            add_(x, tb[j].query(0, x[j]));
        for (int j = 0; j < M; ++j)
            tb[j].update2(pos[j][u], x);
        ta.update2(tin[u], x);
        add_(tc[u], x);
    };

    for (i = 0; i < M; ++i)
        tb.emplace_back(N);

    for (i = 0; i < M; ++i)
        for (j = 1; j < N; ++j)
            ta.update(tin[j], i, pos[i][j]);

    int what = 2;
    if(N>2001)
        what=1;
    for (i = 0; i < what; ++i) {
        for (j = 0; j < N - 1; ++j) {
            int u = S[i][j];
            Put(u, ta.query(tin[u], tout[u]));
        }
    }

    for (i = 1; i < N; ++i) Put(i, ta.query(tin[i], tout[i]));

    Lena at {};
    int K = 0;

    while (1) {
        for (j = 0; j < M; ++j)
            if (at[j] >= N - 1)
                return K;

        for (j = 0; j < M; ++j)
            add_(at, tc[S[j][at[j]]]);

        for (j = 0; j < M; ++j)
            ++at[j];

        ++K;
    }
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 10328 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 10328 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 10588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 10328 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 10588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 10328 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 10588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 10328 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 10588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 10328 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -