Submission #1069816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069816		juicy	Dungeon 2 (JOI16_dungeon2)	C++17	0 / 100	7 ms	860 KiB

dungeon2

#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
• Subtask 2: 0 / 27
• Subtask 3: 0 / 56