oj.uz

Submission #134746

# Submission time Handle Problem Language Result Execution time Memory
134746 2019-07-23T08:28:46 Z 송준혁(#3242) None (JOI16_dungeon2) C++14
0 / 100
 18 ms 784 KB 
#include "dungeon2.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int ans[110], L, N=1;
int adj[110][110];
bool chk[110];
queue<pii> Q;

bool findOne(int u){
	if (chk[u]) return false;
	chk[u] = true;
	for (int i=1; i<=NumberOfRoads(); i++){
		if (!adj[u][i]){
			N++;
			Move(i, 2);
			Move(LastRoad(), 3);
			return true;
		}
		else {
			Move(i, 2);
			bool tf = findOne(adj[u][i]);
			Move(LastRoad(), 2);
			if (tf) return true;
		}
	}
	return false;
}

void FindEdge(int u){
	if (chk[u]) return;
	chk[u] = true;
	for (int i=1; i<=NumberOfRoads(); i++){
		if (!adj[u][i]){
			Move(i, 2);
			if (Color() == 3){
				adj[N][LastRoad()] = u;
				adj[u][i] = N;
			}
			Move(LastRoad(), Color());
		}
		else {
			Move(i, 2);
			FindEdge(adj[u][i]);
			Move(LastRoad(), 2);
		}
	}
}

void Coloring(int u){
	if (chk[u]) return;
	chk[u] = true;
	for (int i=1; i<=NumberOfRoads(); i++){
		if (adj[u][i]){
			Move(i, 2);
			Coloring(adj[u][i]);
			Move(LastRoad(), 2);
		}
	}
}

void Inspect(int R){
	while (findOne(1)){
		memset(chk, false, sizeof chk);
		FindEdge(1);
		memset(chk, false, sizeof chk);
		Coloring(1);
		memset(chk, false, sizeof chk);
	}
	for (int i=1; i<=N; i++){
		memset(chk, false, sizeof chk);
		Q.push(pii(i, 0));
		while(!Q.empty()){
			pii T = Q.front();
			Q.pop();
			if (chk[T.first]) continue;
			chk[T.first] = true;
			ans[T.second]++;
			for (int j=1; adj[T.first][j]; j++) Q.push(pii(adj[T.first][j], T.second+1));
		}
	}
	for (int i=1; i<=R; i++) Answer(i, ans[i]/2);
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 504 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 376 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 784 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -