oj.uz

Submission #39296

# Submission time Handle Problem Language Result Execution time Memory
39296 2018-01-11T03:12:25 Z funcsr None (JOI16_dungeon2) C++14
100 / 100
 26 ms 3100 KB 
#include "dungeon2.h"
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <cassert>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x), x.end()))
#define index(x, y) (int)(lower_bound(all(x), y) - x.begin())
#define pb push_back
#define _1 first
#define _2 second
#define INF 1145141919

int N;
int G[200][200];
int deg[200];
int pe[200];
int to[200][200];

void dfs(int x, int p) {
  deg[x] = NumberOfRoads();
  pe[x] = max(-1, LastRoad()-1);
  if (pe[x] != -1) G[x][pe[x]] = p;
  rep(e, deg[x]) if (e != pe[x]) {
    Move(e+1, 2);
    int c = Color(), back = LastRoad()-1;
    if (c != 1) {
      if (c == 3) G[x][e] = -2;
      else G[x][e] = -1;
      Move(back+1, c);
    }
    else {
      int t = N++;
      G[x][e] = t;
      dfs(t, x);
      Move(back+1, 3);
    }
  }
}
void dfs2(int x, int k) {
  int val = x;
  rep(i, k) val /= 3;
  val = (val%3)+1;

  rep(e, deg[x]) if (e != pe[x]) {
    if (G[x][e] == -2) continue;
    Move(e+1, val);
    int c = Color(), back = LastRoad()-1;
    if (G[x][e] == -1) {
      int v = c-1;
      rep(i, k) v *= 3;
      to[x][e] += v;
      Move(back+1, c);
    }
    else {
      dfs2(G[x][e], k);
    }
  }
  if (pe[x] != -1) Move(pe[x]+1, val);
}

vector<int> G2[200];
int D[200];
int ans[201];

void Inspect(int R) {
  rep(i, 200) rep(j, 200) G[i][j] = -1;
  N = 1;
  dfs(0, -1); // 4M
  assert(N <= 200);
  rep(i, 5) dfs2(0, i); // 2M*5
  rep(x, N) {
    rep(e, deg[x]) {
      if (G[x][e] >= 0) {
        int t = G[x][e];
        G2[x].pb(t);
      }
      if (G[x][e] == -1) {
        int t = to[x][e];
        assert(t < x);
        G2[x].pb(t);
        G2[t].pb(x);
      }
    }
  }
  rep(s, N) {
    queue<int> q;
    rep(i, N) D[i] = INF;
    D[s] = 0;
    q.push(s);
    while (!q.empty()) {
      int x = q.front(); q.pop();
      for (int t : G2[x]) {
        if (D[t] == INF) {
          D[t] = D[x]+1;
          q.push(t);
        }
      }
    }
    rep(i, N) ans[D[i]]++;
  }
  rep(i, R) Answer(i+1, ans[i+1]/2);
}

Subtask #1
17.0 / 17.0

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

Subtask #2
27.0 / 27.0

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

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2836 KB Output is correct
2 Correct 0 ms 2836 KB Output is correct
3 Correct 3 ms 2836 KB Output is correct
4 Correct 16 ms 3100 KB Output is correct
5 Correct 0 ms 2836 KB Output is correct
6 Correct 0 ms 2836 KB Output is correct
7 Correct 0 ms 2836 KB Output is correct
8 Correct 0 ms 2836 KB Output is correct
9 Correct 0 ms 2836 KB Output is correct
10 Correct 0 ms 2836 KB Output is correct
11 Correct 0 ms 2836 KB Output is correct
12 Correct 0 ms 2836 KB Output is correct
13 Correct 0 ms 2968 KB Output is correct
14 Correct 0 ms 2836 KB Output is correct
15 Correct 3 ms 2836 KB Output is correct
16 Correct 3 ms 2968 KB Output is correct
17 Correct 19 ms 3100 KB Output is correct
18 Correct 26 ms 3100 KB Output is correct
19 Correct 19 ms 3100 KB Output is correct