oj.uz

Submission #849427

# Submission time Handle Problem Language Result Execution time Memory
849427 2023-09-14T15:20:43 Z vjudge1 Političari (COCI20_politicari) C++17
70 / 70
 18 ms 6492 KB 
#include<bits/stdc++.h>
#define int long long
#define ll pair<int,int>
using namespace std;

long long a[505][505];
long long danhdau[505][505];
vector<int> elt;
int vt[505][505];
int n,k;

void dfs(int u,int v)
{
    if (danhdau[u][v]==1)
    {
        // k++;
        //elt.pop_back();
        int l=vt[u][v];
        int r=elt.size()-1;
        int leng=r-l+1;
        k-=l;
        k%=leng;
        cout << elt[k+l] << '\n';
        return;
    }
    else
    {
        danhdau[u][v]=1;
        elt.push_back(u);
        vt[u][v]=elt.size()-1;
        if (vt[u][v]==k)
        {
            cout << u;
            return;
        }
        dfs(v,a[v][u]);
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> k;
    k--;
    for (int i=1;i<=n;i++)
    {
        for (int i2=1;i2<=n;i2++)
        {
            cin >> a[i][i2];
        }
    }
    // elt.push_back(1);
    // vt[1][2]=0;
    // danhdau[1]++;
    dfs(1,2);
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 8 ms 5720 KB Output is correct
4 Correct 10 ms 5980 KB Output is correct
5 Correct 13 ms 6236 KB Output is correct
6 Correct 12 ms 6236 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4696 KB Output is correct
9 Correct 4 ms 5212 KB Output is correct
10 Correct 15 ms 5912 KB Output is correct
11 Correct 14 ms 6236 KB Output is correct
12 Correct 18 ms 6492 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 2 ms 4956 KB Output is correct