제출 #1146316

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146316		ind1v	The Ties That Guide Us (CEOI23_incursion)	C++17	큐에 대기중	0 ms	0 KiB

incursion

#include <bits/stdc++.h>
#include "incursion.h"

using namespace std;

const int N = 5e4 + 5;

vector<int> mark(vector<pair<int, int>> F, int safe) {
  vector<int> g[N];
  int n = F.size() + 1;
  for (auto x : F) {
    g[x.first].emplace_back(x.second);
    g[x.second].emplace_back(x.first);
  }
  vector<int> d(n, -1);
  d[safe] = 0;
  queue<int> q;
  q.push(safe);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v : g[u]) {
      if (d[v] == -1) {
        d[v] = d[u] + 1;
        q.push(v);
      }
    }
  }
  return d;
}

void locate(vector<pair<int, int>> F, int curr, int t) {
  vector<int> g[N];
  for (auto x : F) {
    g[x.first].emplace_back(x.second);
    g[x.second].emplace_back(x.first);
  }
  int x = curr;
  set<int> vis;
  if (t == 0) {
    return;
  }
  if (g[x].size() == 1) {
    visit(g[x][0]);
    vis.insert(g[x][0]);
    x = g[x][0];
  } else {
    assert(g[x].size() == 2);
    int y = visit(g[x][0]);
    visit(x);
    int z = visit(g[x][1]);
    visit(x);
    if (y < z) {
      visit(g[x][0]);
      x = g[x][0];
      vis.insert(x);
    } else {
      visit(g[x][1]);;
      x = g[x][1];
      vis.insert(x);
    }
  }
  t--;
  while (t > 0) {
    if (g[x].size() == 1) {
      visit(g[x][0]);
      vis.insert(g[x][0]);
      x = g[x][0];
    } else if (g[x].size() == 2) {
      if (vis.count(g[x][0])) {
        visit(g[x][1]);
        vis.insert(g[x][1]);
        x = g[x][1];
      } else {
        visit(g[x][0]);
        vis.insert(g[x][0]);
        x = g[x][0];
      }
    }
    t--;
  }
  return;
}