제출 #1367406

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1367406		kahoul	The Ties That Guide Us (CEOI23_incursion)	C++20	9 / 100	114 ms	4012 KiB

incursion

#include <vector>
#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 45002;
vector<int> rel[maxn];
vector<int> dist(maxn, maxn + 100);
vector<bool> visited(maxn, 0);

std::vector<int> mark(std::vector<std::pair<int, int>> places, int safe) {
  int n = places.size() + 1;

  queue<int> bfs;
  bfs.push(safe);
  dist[safe] = 0;

  for (int i = 0; i < places.size(); i++) {
    auto [u, v] = places[i];
    rel[u].push_back(v);
    rel[v].push_back(u);
  }

  while (!bfs.empty()) {
    int u = bfs.front();
    bfs.pop();

    if (visited[u]) continue;
    visited[u] = 1;

    for (auto v : rel[u]) {
      if (visited[v]) continue;
      if (dist[v] > dist[u] + 1) {
        dist[v] = dist[u] + 1;
        bfs.push(v);
      }
    }
  }

  vector<int> red_dist;

  for (int i = 1; i <= n; i++) {
    red_dist.push_back(dist[i]);
  }

  return red_dist;
}

void locate(std::vector<std::pair<int, int>> graph, int cur, int t0) {
  for (int i = 0; i < graph.size(); i++) {
    auto [u, v] = graph[i];
    rel[u].push_back(v);
    rel[v].push_back(u);
  }

  if (t0 == 0) return;

  int whereami = cur;

  int t1 = visit(rel[cur][0]);
  visited[rel[cur][0]] = 1;
  whereami = rel[cur][0];

  if (t1 == 0) return;
  
  if (t1 > t0) {
    visit(cur);
    whereami = cur;
  }
  visited[cur] = 1;

  while (true) {
    for (auto v: rel[whereami]) {
      if (visited[v]) continue;
      if (visit(v) == 0) return;
      whereami = v;
      visited[v] = 1;
    }
  }
}

• 서브태스크 0: 0 / 0
• 서브태스크 1: 9 / 30
• 서브태스크 2: 0 / 30
• 서브태스크 3: 0 / 40