Submission #126043

#TimeUsernameProblemLanguageResultExecution timeMemory
126043tinderDungeon 2 (JOI16_dungeon2)C++14
0 / 100
12 ms1656 KiB
#include "dungeon2.h" #include <bits/stdc++.h> using namespace std; struct edge { int id, l, r; edge() {} edge(int id, int l, int r) { this -> id = id, this -> l = l, this -> r = r; } bool operator < (const edge &o) const { id < o.id; } }; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxn = 2e2 + 5; const int inf = 1e5; int deg[maxn], pe[maxn]; int dad[maxn], lvl[maxn]; int N, M; int ptr = 0; map<int, int> t[maxn]; vector<edge> back[maxn]; int wot[maxn]; int g[maxn][maxn]; int AncAtLvl(int u, int l) { assert(lvl[u] > l); while(lvl[u] != l) { u = dad[u]; } return u; } void add_edge(int u, int v) { g[u][v] = g[v][u] = 1; } void discover(int u, int par) { pe[u] = LastRoad(); dad[u] = par; deg[u] = NumberOfRoads(); lvl[u] = u == 1 ? 0 : lvl[par] + 1; for(int i = 1; i <= deg[u]; i++) if(i != pe[u]) { Move(i, 2); if(Color() == 1) { int v = ++ptr; add_edge(u, v); t[u][v] = i; discover(v, u); } else { if(Color() == 2) { back[u].emplace_back(i, 69, 69); } Move(LastRoad(), Color()); } } if(u != 1) { Move(pe[u], 3); } } void dfs(int u) { int col = wot[lvl[u]] ? wot[lvl[u]] : 1; for(edge &e : back[u]) { if(e.l == e.r) continue; Move(e.id, col); if(Color() == 1) { // left e.r = e.l + (e.r - e.l) / 3; } else if(Color() == 2) { // mid e.l = e.l + (e.r - e.l) / 3 + 1; e.r = e.l + (e.r - e.l) / 3 + (e.r - e.l) / 3 + 1; } else { // right e.l = e.l + (e.r - e.l) / 3 + (e.r - e.l) / 3 + 2; } Move(LastRoad(), Color()); } for(auto x : t[u]) { Move(x.second, col); dfs(x.first); } if(u != 1) { Move(pe[u], Color()); } } void Inspect(int R) { for(int i = 1; i <= 200; i++) { for(int j = 1; j <= 200; j++) if(i != j) { g[i][j] = inf; } } discover(++ptr, -1); N = ptr; for(int i = 1; i <= N; i++) { M += deg[i]; } M >>= 1; int mxlvl = 0; for(int i = 1; i <= N; i++) { mxlvl = max(mxlvl, lvl[i]); } if(mxlvl == 1) { // predictable graph goto solution; } for(int i = 1; i <= N; i++) { for(edge &e : back[i]) { e.l = 0, e.r = mxlvl - 2; } } while(true) { int cnt = 0; for(int i = 1; i <= N; i++) { for(edge &e : back[i]) { if(e.l == e.r) { add_edge(i, AncAtLvl(i, e.l)); } else { int d = (e.r - e.l) / 3 + 1; int m1 = e.l + d, m2 = e.l + d + d; for(int j = e.l; j < m1; j++) { wot[j] = 1; } for(int j = m1; j < m2; j++) { wot[j] = 2; } for(int j = m2; j <= e.r; j++) { wot[j] = 3; } cnt++; } } } if(!cnt) break; dfs(1); } #ifdef MYPC for(int i = 1; i <= N; i++) { cout << i << " ---> "; for(int j = 1; j <= N; j++) { if(g[i][j] == 1) { cout << j << ' '; } } cout << endl; } #endif solution : ; for(int k = 1; k <= N; k++) { for(int i = 1; i <= N; i++) { for(int j = 1; j <= N; j++) { g[i][j] = min(g[i][j], g[i][k] + g[k][j]); } } } int ans[maxn]; memset(ans, 0, sizeof ans); for(int i = 1; i <= N; i++) { for(int j = i + 1; j <= N; j++) { ans[g[i][j]]++; } } for(int i = 1; i <= R; i++) { Answer(i, ans[i]); } }

Compilation message (stderr)

dungeon2.cpp: In member function 'bool edge::operator<(const edge&) const':
dungeon2.cpp:12:6: warning: statement has no effect [-Wunused-value]
   id < o.id;
   ~~~^~~~~~
dungeon2.cpp:13:2: warning: no return statement in function returning non-void [-Wreturn-type]
  }
  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...