Submission #849394

# Submission time Handle Problem Language Result Execution time Memory
849394 2023-09-14T14:50:43 Z LTTrungCHL Političari (COCI20_politicari) C++17
35 / 70
359 ms 524288 KB
///***LTT***///
/// ->TUYEN QUOC GIA<- ///
#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("popcnt")
#define int long long
#define endl "\n"
#define F first
#define S second
#define pb push_back
#define CHECKBIT(mask,i) ((mask>>(i) )&1) // == 1 la bat, == 0 la tat
#define OFFBIT(mask,i) ((1<<(i))^mask) // tat bit thu i
#define ONBIT(mask,i) ((1<<(i))mask) // bat bit thu i
using namespace std;
const long long oo = 1e9+7;
const int N = 2 * 1e5 + 10;
int n, a[505][505],  k;
vector <int> ans;
int t[505][505];
bool dd[505][505];
void inp(){
    cin >> n >> k;
//    assert(k <= 100000);
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= n;j++){
            cin >> a[i][j];
        }
    }
    return;
}
void case1(int u,int p,int tt){
    int len = tt - t[a[u][p]][a[a[u][p]][u]];
    int du =(k - (t[a[u][p]][a[a[u][p]][u]] ) )% len ;
    cout << -1;
    cout << ans[(t[a[u][p]][a[a[u][p]][u]]  ) + du - 1ll];
    return;
}
void solve(){
    ans.pb(1);
    ans.pb(2);
    int tt = 2;
    dd[1][2] = true;
    t[1][2] = 1;
    int p = 1;
    int u = 2;
    while (tt <= k){
        int preu = u;
        int prep = p;
        if (dd[a[u][p]][a[a[u][p]][u]]){
            case1(u, p ,tt + 1);
            return;
        }
        t[u][a[u][p]] = tt;
        u = a[u][p];
        p = preu;
        ans.pb(u);
        tt++;
    }
    cout << ans[k - 1];
    return;
}
signed main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    if (fopen("file.inp", "r")){
        freopen("file.inp", "r", stdin);
        freopen("file.out", "w", stdout);
    }
    //int t;
    //cin >> t;
    //while(t--){
    inp();
    solve();
    //}
}
/*
3 100000
0 3 2
3 0 1
1 2 0
*/



Compilation message

politicari.cpp: In function 'void solve()':
politicari.cpp:49:13: warning: unused variable 'prep' [-Wunused-variable]
   49 |         int prep = p;
      |             ^~~~
politicari.cpp: In function 'int main()':
politicari.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         freopen("file.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
politicari.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen("file.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Runtime error 327 ms 524288 KB Execution killed with signal 9
3 Runtime error 352 ms 524288 KB Execution killed with signal 9
4 Runtime error 316 ms 524288 KB Execution killed with signal 9
5 Runtime error 349 ms 524288 KB Execution killed with signal 9
6 Runtime error 359 ms 524288 KB Execution killed with signal 9
7 Correct 1 ms 2396 KB Output is correct
8 Correct 2 ms 3420 KB Output is correct
9 Correct 4 ms 3808 KB Output is correct
10 Correct 11 ms 4828 KB Output is correct
11 Correct 13 ms 4940 KB Output is correct
12 Correct 13 ms 5596 KB Output is correct
13 Runtime error 237 ms 524288 KB Execution killed with signal 9
14 Runtime error 302 ms 524288 KB Execution killed with signal 9