Submission #134587

#	Time	Username	Problem	Language	Result	Execution time	Memory
134587		imeimi2000	Dungeon 2 (JOI16_dungeon2)	C++17	100 / 100	26 ms	1656 KiB

dungeon2

#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 (stderr)

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