Submission #1146327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146327		ind1v	The Ties That Guide Us (CEOI23_incursion)	C++17	0 / 100	50 ms	4596 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 - 1].emplace_back(x.second - 1);
    g[x.second - 1].emplace_back(x.first - 1);
  }
  vector<int> d(n, -1);
  safe--;
  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;
  }
  vis.insert(x);
  if (g[x].size() == 1) {
    assert(visit(g[x][0]) == t - 1);
    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) {
      assert(visit(g[x][0]) == t - 1);
      x = g[x][0];
      vis.insert(x);
    } else {
      assert(visit(g[x][1]) == t - 1);
      x = g[x][1];
      vis.insert(x);
    }
  }
  t--;
  while (t > 0) {
    if (g[x].size() == 1) {
//      assert(visit(g[x][0]) == t - 1);
      vis.insert(g[x][0]);
      x = g[x][0];
    } else if (g[x].size() == 2) {
      if (vis.count(g[x][0])) {
//        assert(visit(g[x][1]) == t - 1);
        vis.insert(g[x][1]);
        x = g[x][1];
      } else {
//        assert(vis.count(g[x][1]));
//        assert(visit(g[x][0]) == t - 1);
        vis.insert(g[x][0]);
        x = g[x][0];
      }
    }
    t--;
  }
  return;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40