oj.uz

Submission #1027656

# Submission time Handle Problem Language Result Execution time Memory
1027656 2024-07-19T08:28:58 Z 우민규(#10951) None (JOI16_dungeon2) C++14
0 / 100
 2 ms 600 KB 
#include "dungeon2.h"

#include <bits/stdc++.h>
using namespace std;
// edge no, is back-edge?, is going back (depth decreasing)?
vector<tuple<int, bool, bool>> dfs_travel;
vector<pair<int, int>> saw;

enum DfsState {
  Unvisited = 1,
  Visiting,
  Left,
};

void dfs() {
  int back = LastRoad();
  int num_roads = NumberOfRoads();
  for (int i = 0; i < num_roads; ++i) {
    if (i + 1 == back) continue;
    dfs_travel.push_back({i, false, false});
    Move(i + 1, Visiting);

    int back2 = LastRoad();

    switch (Color()) {
      case Unvisited:
        dfs();
        dfs_travel.push_back({back2 - 1, false, true});
        break;
      case Visiting:
        dfs_travel.back() = {i, true, true};
        dfs_travel.push_back({back2 - 1, true, false});
        break;
      case Left:
        // going to already-visited child
        dfs_travel.pop_back();
        break;
    }
    Move(back2, Left);
  }
}

void Inspect(int r) {
  dfs();
  saw.assign(dfs_travel.size(), {0, 0});
  int n;
  for (int chunk = 1; chunk < 200; chunk *= 3) {
    int cur = 0;
    int travel_idx = 0;
    bool is_new_node = true;
    for (auto [edge, is_back_edge, is_going_back] : dfs_travel) {
      int color = is_new_node ? 1 + (cur / chunk) % 3 : Color();
      if (!is_back_edge && !is_going_back) {
        // going to new node, so assign
        is_new_node = true;
        cur += 1;
      } else {
        is_new_node = false;
      }

      if (is_going_back) {
        int u_color = color - 1;
        Move(edge + 1, color);
        int v_color = Color() - 1;
        saw[travel_idx].first += u_color * chunk;
        saw[travel_idx].second += v_color * chunk;
      } else {
        // depth increasing, could be back edge
        Move(edge + 1, color);
      }

      travel_idx += 1;
    }
    n = cur + 1;
  }
  vector<vector<int>> adj(n);
  for (int i = 0; i < saw.size(); ++i) {
    // is_going_back
    if (get<2>(dfs_travel[i])) {
      adj[saw[i].first].push_back(saw[i].second);
      adj[saw[i].second].push_back(saw[i].first);
    }
  }
  vector<int> answers(max(n, r + 1));
  //   vector<int> answers(n);
  for (int src = 0; src < n; ++src) {
    // do bfs on src
    queue<pair<int, int>> q;
    vector<int> dist(n, INT_MAX);
    dist[src] = 0;
    q.push({0, src});
    while (!q.empty()) {
      auto [d, node] = q.front();
      q.pop();
      for (auto v : adj[node]) {
        if (dist[v] > d + 1) {
          dist[v] = d + 1;
          q.push({d + 1, v});
        }
      }
    }
    for (int i = 0; i < n; ++i) {
      assert(dist[i] != INT_MAX);
      answers[dist[i]] += 1;
    }
  }
  for (int i = 1; i <= r; ++i) {
    Answer(i, answers[i] / 2);
  }
}

#ifndef EVAL
#include "grader.cpp"
#endif

Compilation message

dungeon2.cpp: In function 'void Inspect(int)':
dungeon2.cpp:51:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |     for (auto [edge, is_back_edge, is_going_back] : dfs_travel) {
      |               ^
dungeon2.cpp:77:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for (int i = 0; i < saw.size(); ++i) {
      |                   ~~^~~~~~~~~~~~
dungeon2.cpp:93:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   93 |       auto [d, node] = q.front();
      |            ^

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 0 ms 348 KB Wrong Answer [4]
5 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 600 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -