oj.uz

답안 #26172

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26172 2017-06-28T08:01:56 Z 윤교준(#1099) Dungeon 2 (JOI16_dungeon2) C++11
90 / 100
 23 ms 3088 KB 
#include "dungeon2.h"
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#include <tuple>
#define rf(x) (x)=0;while(*p<48)im=*p=='-';while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);if(im)(x)=-(x);
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (1010000099)
#define INFLL (1010000000000000099ll)
#define MAXN (205)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
int NOR() { return NumberOfRoads(); }
const int THREE[5] = {1, 3, 9, 27, 81};

vector<int> G[MAXN]; // -1 : Wo, -2 : De
vector<int> Q[MAXN];
int d[MAXN][MAXN];
int TT[5][MAXN];
int Ans[MAXN];
int N;

int dfs1(int prteidx) {
	if(3 == Color()) {
		Move(prteidx, 3);
		return -3;
	}
	if(2 == Color()) {
		Move(prteidx, 2);
		return -2;
	}
	N++; G[N].resize(NOR()); int ret = N;
	for(int i = 1; i <= NOR(); i++) {
		Move(i, 2);
		G[ret][i-1] = dfs1(LastRoad());
	}
	if(-1 != prteidx) Move(prteidx, 3);
	return ret;
}
void dfs2(int TT[], int THREE, int idx, int prteidx, bool isfinal) {
	for(int i = 1; i <= NOR(); i++) {
		int nxt = G[idx][i-1];
		if(-3 == nxt) continue;
		if(-2 == nxt) {
			Move(i, TT[idx] + 1);
			Q[idx][i-1] += THREE * (Color() - 1);
			if(isfinal) {
				Q[Q[idx][i-1]][LastRoad()-1] = idx;
			}
			Move(LastRoad(), Color());
		} else {
			Move(i, TT[idx] + 1);
			dfs2(TT, THREE, nxt, LastRoad(), isfinal);
		}
	}
	if(-1 != prteidx) Move(prteidx, TT[idx] + 1);
}
void Inspect(int R) {
	dfs1(-1);
	for(int i = 1; i <= N; i++) {
		for(int t = i, c = 0; c < 5; t /= 3, c++) TT[c][i] = t%3;
	}
	for(int i = 1; i <= N; i++) Q[i].resize(sz(G[i]));
	for(int i = 0; i < 5; i++) dfs2(TT[i], THREE[i], 1, -1, 4 == i);
	for(int i = 1; i <= N; i++) {
		for(int j = 0; j < sz(G[i]); j++) {
			if(0 < G[i][j]) continue;
			G[i][j] = Q[i][j];
		}
	}
	/*printf("%d\n", N);
	for(int i = 1; i <= N; i++) {
		printf("G %d\n", i);
		for(int v : G[i]) printf("%d ", v); puts("");
	}*/
	for(int i = 0; i < MAXN; i++) fill(d[i], d[i]+MAXN, INF);
	for(int i = 1; i <= N; i++) for(int v : G[i]) d[i][v] = d[v][i] = 1;
	for(int i = 1; i <= N; i++) d[i][i] = 0;
	for(int k = 1; k <= N; k++) for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++)
		upmin(d[i][j], d[i][k]+d[k][j]);
	//for(int i = 1; i <= N; i++, puts("")) for(int j = 1; j <= N; j++) printf("%d ", d[i][j]);
	for(int i = 1; i <= N; i++) for(int j = i+1; j <= N; j++) Ans[d[i][j]]++;
	for(int i = 1; i <= R; i++) Answer(i, Ans[i]);
}

Subtask #1
17.0 / 17.0

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

Subtask #2
27.0 / 27.0

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

Subtask #3
46.0 / 56.0

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