제출 #27176

#제출 시각아이디문제언어결과실행 시간메모리
27176abcdef6199Dungeon 2 (JOI16_dungeon2)C++98
0 / 100
0 ms4572 KiB
#include "dungeon2.h" #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> II; const int MAXN = 500 + 10; int n, a[MAXN][MAXN]; int ans[MAXN][MAXN]; vector<II> adj[MAXN]; vector<int> ret[MAXN]; void Build(int u) { int deg = NumberOfRoads(); int pre = LastRoad(); for (int i = 1; i <= deg; ++i) if (i != pre) { Move(i, 2); int x = LastRoad(); if (Color() == 1) { adj[u].push_back(II(++n, i)); Build(n); Move(x, 3); } else { int c = Color(); if (c == 2) ret[u].push_back(i); Move(x, c); } } } void DFS(int u, int pw, vector<int> ver) { int h = (int) ver.size(); for (int j = 0; j < (int) ret[u].size(); ++j) { int i = ret[u][j]; Move(i, h % (pw * 3) / pw + 1); int x = LastRoad(); int c = Color(); ans[u][i] += pw * (c - 1); Move(x, c); if (pw == 81) { assert(ans[u][i] < (int) ver.size()); int v = ver[ans[u][i]]; a[u][v] = 1; a[v][u] = 1; } } ver.push_back(u); for (int j = 0; j < (int) adj[u].size(); ++j) { int i = adj[u][j].second; Move(i, h % (pw * 3) / pw + 1); int x = LastRoad(); DFS(adj[u][j].first, pw, ver); Move(x, Color()); } ver.pop_back(); } void Inspect(int R) { n = 1; Build(1); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) a[i][j] = 100000; a[i][i] = 0; } for (int i = 1; i <= n; ++i) { for (int j = 0; j < (int) adj[i].size(); ++j) { int x = adj[i][j].first; a[i][x] = 1; a[x][i] = 1; } } DFS(1, 1, vector<int>(0, 0)); DFS(1, 3, vector<int>(0, 0)); return; DFS(1, 9, vector<int>(0, 0)); DFS(1, 27, vector<int>(0, 0)); DFS(1, 81, vector<int>(0, 0)); for (int k = 1; k <= n; ++k) for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) a[i][j] = min(a[i][j], a[i][k] + a[k][j]); for (int i = 1; i <= R; ++i) { int ans = 0; for (int u = 1; u <= n; ++u) for (int v = u + 1; v <= n; ++v) if (a[u][v] == i) ans++; Answer(i, ans); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...