oj.uz

Submission #134587

# Submission time Handle Problem Language Result Execution time Memory
134587 2019-07-23T04:49:53 Z imeimi2000 None (JOI16_dungeon2) C++17
100 / 100
 26 ms 1656 KB 
#include "dungeon2.h"
#include <vector>
 
using namespace std;
 
int ord;
vector<int> edge[200];
vector<int> depth[200];
int dep[200];
int par[200];
int parEdge[200];
int pro(int p, int d) {
    int c = Color();
    if (c > 1) {
        Move(LastRoad(), c);
        return 1 - c;
    }
    
    int x = ord++;
    par[x] = p;
    dep[x] = d;
    int l = LastRoad() - 1;
    parEdge[x] = l;
    edge[x].resize(NumberOfRoads());
    depth[x].resize(edge[x].size(), 0);
    if (p != -1) edge[x][l] = p;
    for (int i = 0; i < edge[x].size(); ++i) {
        if (i == l) continue;
        Move(i + 1, 2);
        edge[x][i] = pro(x, d + 1);
    }
    
    if (p != -1) Move(l + 1, 3);
    return x;
}
 
void getDis(int x, int d, int gr) {
    int c = d / gr % 3 + 1;
    for (int i = 0; i < edge[x].size(); ++i) {
        if (edge[x][i] == -2) continue;
        if (edge[x][i] == -1) {
            Move(i + 1, c);
            depth[x][i] += gr * (Color() - 1);
            Move(LastRoad(), Color());
        }
        else if (edge[x][i] != par[x]) {
            Move(i + 1, c);
            getDis(edge[x][i], d + 1, gr);
        }
    }
    
    if (par[x] != -1) Move(parEdge[x] + 1, c);
}
 
int ans[1000001];
int dist[200][200];
const int inf = 1e6;
void Inspect(int R) {
	pro(-1, 0);
	for (int i = 81; i > 0; i /= 3) getDis(0, 0, i);
	for (int i = 0; i < ord; ++i) {
        for (int j = 0; j < ord; ++j) {
            dist[i][j] = inf;
        }
        dist[i][i] = 0;
	}
	for (int i = 0; i < ord; ++i) {
        for (int j = 0; j < edge[i].size(); ++j) {
            if (edge[i][j] == -2) continue;
            if (edge[i][j] == -1) {
                int x = i;
                for (int it = dep[i] - depth[i][j]; it--; ) x = par[x];
                dist[x][i] = dist[i][x] = 1;
            }
            else {
                dist[i][edge[i][j]] = 1;
            }
        }
	}
	
	for (int k = 0; k < ord; ++k) {
        for (int i = 0; i < ord; ++i) {
            for (int j = 0; j < ord; ++j) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
	}
	for (int i = 0; i < ord; ++i) {
        for (int j = 0; j < i; ++j) {
            ++ans[dist[i][j]];
        }
	}
	for (int i = 1; i <= R; ++i) {
        Answer(i, ans[i]);
	}
}

Compilation message

dungeon2.cpp: In function 'int pro(int, int)':
dungeon2.cpp:27:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < edge[x].size(); ++i) {
                     ~~^~~~~~~~~~~~~~~~
dungeon2.cpp: In function 'void getDis(int, int, int)':
dungeon2.cpp:39:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < edge[x].size(); ++i) {
                     ~~^~~~~~~~~~~~~~~~
dungeon2.cpp: In function 'void Inspect(int)':
dungeon2.cpp:68:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < edge[i].size(); ++j) {
                         ~~^~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 508 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 476 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 2 ms 504 KB Output is correct
14 Correct 2 ms 504 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 2 ms 508 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 2 ms 632 KB Output is correct
15 Correct 2 ms 504 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 888 KB Output is correct
2 Correct 12 ms 980 KB Output is correct
3 Correct 12 ms 888 KB Output is correct
4 Correct 26 ms 1528 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 5 ms 760 KB Output is correct
7 Correct 13 ms 1016 KB Output is correct
8 Correct 12 ms 892 KB Output is correct
9 Correct 13 ms 888 KB Output is correct
10 Correct 12 ms 888 KB Output is correct
11 Correct 12 ms 888 KB Output is correct
12 Correct 12 ms 888 KB Output is correct
13 Correct 14 ms 1016 KB Output is correct
14 Correct 12 ms 888 KB Output is correct
15 Correct 12 ms 888 KB Output is correct
16 Correct 6 ms 760 KB Output is correct
17 Correct 25 ms 1528 KB Output is correct
18 Correct 25 ms 1656 KB Output is correct
19 Correct 24 ms 1400 KB Output is correct