oj.uz

Submission #1069816

# Submission time Handle Problem Language Result Execution time Memory
1069816 2024-08-22T09:10:16 Z juicy None (JOI16_dungeon2) C++17
0 / 100
 7 ms 860 KB 
#include "dungeon2.h"

#include <bits/stdc++.h>

using namespace std;

namespace {
    const int N = 200, LG = 5;

    int n;
    int d[N][N], deg[N], res[N], pr[N];
    vector<array<int, 2>> tree[N], back[N];

    void init() {
        int u = n++;
        deg[u] = NumberOfRoads();
        for (int i = 1; i <= deg[u]; ++i) {
            if (i == pr[u]) {
                continue;
            }
            Move(i, 2);
            int c = Color();
            int ind = LastRoad();
            if (c == 1) {
                pr[n] = ind;
                tree[u].push_back({n, i});
                init();
                Move(ind, 3);
            } else if (c == 2) {
                back[u].push_back({i, 0});
                Move(ind, 2);
            } else {
                Move(ind, 3);
            }
        }
    }

    void dfs(int u, int x) {
        int c = (u / x) % 3 + 1;
        for (auto &[v, ind] : back[u]) {
            Move(v, c);
            int w = Color();
            ind += (w - 1) * x;
            Move(LastRoad(), w);
        }
        for (auto [v, ind] : tree[u]) {
            Move(ind, c);
            int i = LastRoad();
            dfs(v, x);
            Move(i, 3);
        }
    }
}

void Inspect(int R) {
    init();
    for (int i = 1, j = 0; j < 5; i *= 3, ++j) {
        dfs(0, i);
    }
    for (int i = 0; i < n; ++i) {
        fill(d[i], d[i] + n, N + 1);
        d[i][i] = 0;
        for (auto [j, ind] : tree[i]) {
            d[i][j] = d[j][i] = 1;
        }
        for (auto [ind, j] : back[i]) {
            d[i][j] = d[j][i] = 1;
        }
    }
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (d[i][j] <= R) {
                ++res[d[i][j] - 1];
            }
        }
    }
    for (int i = 1; i <= R; ++i) {
        Answer(i, res[i - 1]);
    }
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 860 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -