제출 #238069

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
238069		Haunted_Cpp	Političari (COCI20_politicari)	C++17	0 / 70	25 ms	2304 KiB

politicari

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

const int N = 5e2 + 5;

bitset<N> vis [N];
vector<pair<int, int> > who;

int g [N][N];

int ciclo = -1;

void dfs (int node, int p) {
  if (vis[node][p]) {
    ciclo = find (who.begin(), who.end(), make_pair(node, p) ) - who.begin();
    return;
  }
  who.emplace_back(node, p);
  vis[node][p] = 1;
  dfs (g[node][p], node);
}

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  long long k;
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> g[i][j];
      --g[i][j];
    }
  }
  who.emplace_back(0, -1);
  dfs (1, 0);
  --k;
  if (k < ciclo) {
    cout << who[ciclo].first + 1 << '\n';
  } else {
    int t = (int) who.size() - ciclo + 1;
    k %= t;
    cout << who[ciclo + k].first + 1 << '\n';
  }
  return 0;
}

• Subtask 1: 0 / 70