oj.uz

Submission #69043

# Submission time Handle Problem Language Result Execution time Memory
69043 2018-08-19T15:00:16 Z reality None (JOI16_dungeon2) C++17
100 / 100
 42 ms 1588 KB 
#include "dungeon2.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define vii vector < pii >
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 256;
int deg[N];
int roads[N][N];
vector < pii > g[N];
vi G[N];
int pr[N];
int D[N][N];
int ans[N];
int n;
void dfs(int node) {
	pr[node] = LastRoad();
	deg[node] = NumberOfRoads();
	for (int i = 1;i <= deg[node];++i) 
		if (pr[node] != i) {
		Move(i,2);
		int col = Color();
		if (col == 1) {
			g[node].pb(mp(i,++n));
			dfs(n);
		} else {
			if (col == 2)
				G[node].pb(i);
			Move(LastRoad(),col);
		}
	}
	if (pr[node] != -1)
		Move(pr[node],3);
}
void DFS(int node,int K) {
	for (auto it : G[node]) {
		Move(it,(node / K) % 3 + 1);
		roads[node][it] += (Color() - 1) * K;
		Move(LastRoad(),Color());
	}
	for (auto it : g[node]) {
		Move(it.fi,(node / K) % 3 + 1);
		DFS(it.se,K);
	}
	if (pr[node] != -1)
		Move(pr[node],(node / K) % 3 + 1);
}
void Inspect(int R) {
	dfs(++n);
	int pw = 1;
	for (int i = 0;i < 5;++i) {
		DFS(1,pw);
		pw *= 3;
	}
	for (int i = 1;i <= n;++i)
		for (int j = 1;j <= n;++j)
			if (i != j)
				D[i][j] = 1e9;
	for (int i = 1;i <= n;++i) {
		for (int j = 1;j <= deg[i];++j)
			if (roads[i][j])
				D[i][roads[i][j]] = D[roads[i][j]][i] = 1;
		for (auto it : g[i])
			D[i][it.se] = D[it.se][i] = 1;
	}
	for (int k = 1;k <= n;++k)
		for (int i = 1;i <= n;++i)
			for (int j = 1;j <= n;++j)
				D[i][j] = min(D[i][j],D[i][k] + D[k][j]);
	for (int i = 1;i <= n;++i)
		for (int j = 1;j < i;++j)
			if (D[i][j] <= R)
				ans[D[i][j]] += 1;
	for (int i = 1;i <= R;++i)
		Answer(i,ans[i]);
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 612 KB Output is correct
3 Correct 3 ms 692 KB Output is correct
4 Correct 3 ms 692 KB Output is correct
5 Correct 3 ms 692 KB Output is correct
6 Correct 3 ms 692 KB Output is correct
7 Correct 3 ms 828 KB Output is correct
8 Correct 3 ms 828 KB Output is correct
9 Correct 3 ms 828 KB Output is correct
10 Correct 3 ms 828 KB Output is correct
11 Correct 3 ms 828 KB Output is correct
12 Correct 3 ms 828 KB Output is correct
13 Correct 2 ms 828 KB Output is correct
14 Correct 3 ms 828 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 828 KB Output is correct
2 Correct 4 ms 828 KB Output is correct
3 Correct 3 ms 828 KB Output is correct
4 Correct 3 ms 828 KB Output is correct
5 Correct 3 ms 840 KB Output is correct
6 Correct 3 ms 840 KB Output is correct
7 Correct 2 ms 840 KB Output is correct
8 Correct 3 ms 840 KB Output is correct
9 Correct 3 ms 840 KB Output is correct
10 Correct 3 ms 840 KB Output is correct
11 Correct 2 ms 840 KB Output is correct
12 Correct 3 ms 840 KB Output is correct
13 Correct 4 ms 840 KB Output is correct
14 Correct 3 ms 840 KB Output is correct
15 Correct 2 ms 840 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1404 KB Output is correct
2 Correct 17 ms 1404 KB Output is correct
3 Correct 14 ms 1404 KB Output is correct
4 Correct 40 ms 1588 KB Output is correct
5 Correct 3 ms 1588 KB Output is correct
6 Correct 6 ms 1588 KB Output is correct
7 Correct 20 ms 1588 KB Output is correct
8 Correct 25 ms 1588 KB Output is correct
9 Correct 16 ms 1588 KB Output is correct
10 Correct 14 ms 1588 KB Output is correct
11 Correct 13 ms 1588 KB Output is correct
12 Correct 15 ms 1588 KB Output is correct
13 Correct 16 ms 1588 KB Output is correct
14 Correct 15 ms 1588 KB Output is correct
15 Correct 17 ms 1588 KB Output is correct
16 Correct 9 ms 1588 KB Output is correct
17 Correct 26 ms 1588 KB Output is correct
18 Correct 42 ms 1588 KB Output is correct
19 Correct 29 ms 1588 KB Output is correct