Submission #26200

#	Time	Username	Problem	Language	Result	Execution time	Memory
26200		tlwpdus	Dungeon 2 (JOI16_dungeon2)	C++98	90 / 100	23 ms	3048 KiB

dungeon2

#include "dungeon2.h"
#include <bits/stdc++.h>

using namespace std;

/*
void Answer(int D, int A)
void Move(int I, int C)
int NumberOfRoads()
int LastRoad()
int Color()
*/

int lis[210][210];
int tis[210][210];
int n;
void dfs(int here) {
    int sz = NumberOfRoads(), q, i;
    for (i=1;i<=sz;i++) {
        bool flag = false;
        Move(i,2); q = LastRoad();
        if (Color()==1) {
            tis[here][i-1] = lis[here][i-1] = n;
            dfs(n++);
            flag = true;
        }
        else if (Color()==2) {
            tis[here][i-1] = 0;
            lis[here][i-1] = -1;
        }
        else lis[here][i-1] = -2;
        Move(q,(flag)?3:Color());
    }
}

int getd(int num, int loc) {
    int i;
    for (i=0;i<loc;i++,num/=3);
    return num%3+1;
}

int bit(int dig, int loc) {
    int i;
    for (i=0;i<loc;i++,dig*=3);
    return dig;
}

void adfs(int here, int loc) {
    int sz = NumberOfRoads(), q, i;
    for (i=1;i<=sz;i++) {
        bool flag = false;
        if (lis[here][i-1]==-2) {
            tis[here][i-1]=lis[here][i-1];
            continue;
        }
        Move(i,getd(here,loc)); q = LastRoad();
        if (lis[here][i-1]<0) {
            tis[here][i-1] += bit(Color()-1,loc);
        }
        else {
            adfs(lis[here][i-1],loc);
            flag = true;
        }
        Move(q,(flag)?getd(lis[here][i-1],loc):Color());
    }
}

void init() {
    dfs(n++);
}

const int INF = 987654321;
int mat[220][220];
int res[220];

void floyd() {
    int i, j, k;
    for (k=0;k<n;k++) {
        for (i=0;i<n;i++) {
            for (j=0;j<n;j++) {
                if (mat[i][j]>mat[i][k]+mat[k][j]) {
                    mat[i][j]=mat[i][k]+mat[k][j];
                }
            }
        }
    }
    for (i=0;i<n;i++) for (j=i+1;j<n;j++) if (mat[i][j]<=n) res[mat[i][j]]++;
}

void Inspect(int R) {
	int i, j;
	for (i=0;i<200;i++) for (j=0;j<200;j++) tis[i][j] = -2;
	init();
	for (i=0;i<n;i++) for (j=0;j<n;j++) if (i!=j) mat[i][j] = INF;
	for (i=0;i<5;i++) adfs(0,i);

	for (i=0;i<n;i++) for (j=0;j<n;j++) if (tis[i][j]>=0) mat[i][tis[i][j]] = mat[tis[i][j]][i] = 1;

	floyd();
	for (i=1;i<=R;i++) Answer(i,res[i]);
}

• Subtask 1: 17 / 17
• Subtask 2: 27 / 27
• Subtask 3: 46 / 56