oj.uz

Submission #849400

# Submission time Handle Problem Language Result Execution time Memory
849400 2023-09-14T14:52:57 Z LTTrungCHL Političari (COCI20_politicari) C++17
35 / 70
 115 ms 138452 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 << 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++;
        if (ans.size() > 10000000){
            cout << -1;
            exit(0);
        }
    }
    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:48:13: warning: unused variable 'prep' [-Wunused-variable]
   48 |         int prep = p;
      |             ^~~~
politicari.cpp: In function 'int main()':
politicari.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen("file.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
politicari.cpp:72:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         freopen("file.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 96 ms 135184 KB Output isn't correct
3 Incorrect 96 ms 137000 KB Output isn't correct
4 Incorrect 97 ms 135832 KB Output isn't correct
5 Incorrect 115 ms 138452 KB Output isn't correct
6 Incorrect 112 ms 137432 KB Output isn't correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 2 ms 3416 KB Output is correct
9 Correct 4 ms 3804 KB Output is correct
10 Correct 11 ms 4828 KB Output is correct
11 Correct 13 ms 5084 KB Output is correct
12 Correct 14 ms 5656 KB Output is correct
13 Incorrect 70 ms 135580 KB Output isn't correct
14 Incorrect 87 ms 134492 KB Output isn't correct