Submission #238070

#	Time	Username	Problem	Language	Result	Execution time	Memory
238070		Haunted_Cpp	Političari (COCI20_politicari)	C++17	70 / 70	24 ms	1408 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]) {
 //   cout << "YH: " << node << ' ' << p << '\n';
    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;
 // for (auto to : who) cout << to.first << ' '<< to.second << '\n';
  if (k < ciclo) {
    cout << who[k].first + 1 << '\n';
  } else {
    k -= ciclo;
    int t = (int) who.size() - ciclo;
    k %= t;
 //   cout << "Y: " << t << ' ' << k << '\n';
    cout << who[ciclo + k].first + 1 << '\n';
  }
  return 0;
}

• Subtask 1: 70 / 70