oj.uz

답안 #26200

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26200 2017-06-28T10:28:14 Z tlwpdus Dungeon 2 (JOI16_dungeon2) C++
90 / 100
 23 ms 3048 KB 
#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.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 3048 KB Output is correct
2 Correct 0 ms 3048 KB Output is correct
3 Correct 0 ms 3048 KB Output is correct
4 Correct 0 ms 3048 KB Output is correct
5 Correct 0 ms 3048 KB Output is correct
6 Correct 0 ms 3048 KB Output is correct
7 Correct 0 ms 3048 KB Output is correct
8 Correct 0 ms 3048 KB Output is correct
9 Correct 0 ms 3048 KB Output is correct
10 Correct 0 ms 3048 KB Output is correct
11 Correct 0 ms 3048 KB Output is correct
12 Correct 0 ms 3048 KB Output is correct
13 Correct 0 ms 3048 KB Output is correct
14 Correct 0 ms 3048 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 3048 KB Output is correct
2 Correct 0 ms 3048 KB Output is correct
3 Correct 0 ms 3048 KB Output is correct
4 Correct 0 ms 3048 KB Output is correct
5 Correct 0 ms 3048 KB Output is correct
6 Correct 0 ms 3048 KB Output is correct
7 Correct 0 ms 3048 KB Output is correct
8 Correct 0 ms 3048 KB Output is correct
9 Correct 0 ms 3048 KB Output is correct
10 Correct 0 ms 3048 KB Output is correct
11 Correct 0 ms 3048 KB Output is correct
12 Correct 0 ms 3048 KB Output is correct
13 Correct 0 ms 3048 KB Output is correct
14 Correct 0 ms 3048 KB Output is correct
15 Correct 0 ms 3048 KB Output is correct

Subtask #3
46.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 6 ms 3048 KB Partially correct
2 Partially correct 6 ms 3048 KB Partially correct
3 Partially correct 9 ms 3048 KB Partially correct
4 Partially correct 16 ms 3048 KB Partially correct
5 Partially correct 0 ms 3048 KB Partially correct
6 Partially correct 3 ms 3048 KB Partially correct
7 Partially correct 6 ms 3048 KB Partially correct
8 Partially correct 6 ms 3048 KB Partially correct
9 Partially correct 6 ms 3048 KB Partially correct
10 Partially correct 6 ms 3048 KB Partially correct
11 Partially correct 9 ms 3048 KB Partially correct
12 Partially correct 6 ms 3048 KB Partially correct
13 Partially correct 9 ms 3048 KB Partially correct
14 Partially correct 6 ms 3048 KB Partially correct
15 Partially correct 9 ms 3048 KB Partially correct
16 Partially correct 3 ms 3048 KB Partially correct
17 Partially correct 19 ms 3048 KB Partially correct
18 Partially correct 19 ms 3048 KB Partially correct
19 Partially correct 23 ms 3048 KB Partially correct