oj.uz

Submission #849288

# Submission time Handle Problem Language Result Execution time Memory
849288 2023-09-14T11:40:06 Z mickey080929 None (JOI16_dungeon2) C++17
100 / 100
 17 ms 1376 KB 
#include "dungeon2.h"
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;

const int inf = 1e9;

pii par[210];
vector<pii> up[210];
vector<pii> down[210];
int n;
int dist[210][210];
int ans[210];

int make_dfs_tree(int p) {
    if (Color() == 2) {
        Move(LastRoad(), 2);
        return 0;
    }
    if (Color() == 3) {
        Move(LastRoad(), 3);
        return -1;
    }
    int x = ++ n;
    par[x] = {LastRoad(), p};
    int deg = NumberOfRoads();
    for (int i=1; i<=deg; i++) {
        if (i == par[x].first) continue;
        Move(i, 2);
        int ret = make_dfs_tree(x);
        if (ret == 0) up[x].emplace_back(i, 0);
        else if (ret > 0) down[x].emplace_back(i, ret);
    }
    if (x != 1) Move(par[x].first, 3);
    return x;
}

void dfs(int x, int step) {
    for (auto &[road, num] : up[x]) {
        Move(road, 1);
        num = num + (Color() - 1) * step;
        Move(LastRoad(), Color());
    }
    int digit = x / step % 3;
    for (auto &[road, num] : down[x]) {
        Move(road, digit+1);
        dfs(num, step);
    }
    if (x != 1) Move(par[x].first, 1);
}

void Inspect(int R) {
	make_dfs_tree(-1);
	int step = 1;
	for (int i=0; i<5; i++) dfs(1, step), step *= 3;
	for (int i=1; i<=n; i++)
        for (int j=i+1; j<=n; j++)
            dist[i][j] = dist[j][i] = inf;
	for (int i=1; i<=n; i++) {
        for (auto &[road, num] : up[i])
            dist[i][num] = dist[num][i] = 1;
        if (i != 1)
            dist[i][par[i].second] = dist[par[i].second][i] = 1;
	}
    for (int k=1; k<=n; k++)
        for (int i=1; i<=n; i++)
            for (int j=1; j<=n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    for (int i=1; i<=n; i++)
        for (int j=i+1; j<=n; j++)
            ans[dist[i][j]] ++;
    for (int i=1; i<=R; i++)
        Answer(i, ans[i]);
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 856 KB Output is correct
13 Correct 1 ms 756 KB Output is correct
14 Correct 1 ms 604 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 356 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 856 KB Output is correct
2 Correct 8 ms 856 KB Output is correct
3 Correct 8 ms 856 KB Output is correct
4 Correct 14 ms 1364 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 3 ms 600 KB Output is correct
7 Correct 8 ms 856 KB Output is correct
8 Correct 8 ms 856 KB Output is correct
9 Correct 8 ms 856 KB Output is correct
10 Correct 8 ms 856 KB Output is correct
11 Correct 9 ms 856 KB Output is correct
12 Correct 8 ms 856 KB Output is correct
13 Correct 9 ms 1112 KB Output is correct
14 Correct 8 ms 1112 KB Output is correct
15 Correct 9 ms 1112 KB Output is correct
16 Correct 3 ms 860 KB Output is correct
17 Correct 17 ms 1368 KB Output is correct
18 Correct 17 ms 1376 KB Output is correct
19 Correct 13 ms 1372 KB Output is correct