oj.uz

답안 #279669

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
279669 2020-08-22T09:41:35 Z PedroBigMan Političari (COCI20_politicari) C++14
70 / 70
 25 ms 3328 KB 
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=a; i<b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 5000000000000000000LL

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

struct hash_pair 
{ 
    template <class T1, class T2> 
    size_t operator() (pair<T1, T2> p) const
    {
        size_t hash1 = hash<T1>()(p.first); 
        size_t hash2 = hash<T2>()(p.second); 
        return (hash1 ^ hash2); 
    } 
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll N,K; cin>>N>>K;
    vector<vector<ll> > a; vector<ll> xx; REP(i,0,N) {xx.pb(0LL);} REP(i,0,N) {a.pb(xx);}
    REP(i,0,N) {REP(j,0,N) {cin>>a[i][j]; a[i][j]--;}}
    vector<ll> cur; cur.pb(0); cur.pb(1); unordered_map<pl,ll,hash_pair> m;
    m[mp(0,1)]=0;
    ll nxt; pl l;
    pl per;
    REP(i,2,INF)
    {
        nxt = a[cur[i-1]][cur[i-2]];
        l = mp(cur[i-1],nxt);
        if(m.find(l)!=m.end()) 
        {
            per.ff=m[l]; per.ss=i-2; break;
        }
        else {m[l]=i-1; cur.pb(nxt);}
    }
    K--;
    if(K<per.ff) {cout<<cur[K]+1<<endl; return 0;}
    K-=per.ff; K%=(per.ss-per.ff+1LL); if(K<0) {K+=(per.ss-per.ff+1LL);}
    K+=per.ff;
    cout<<cur[K]+1<<endl;
    return 0;
}

Subtask #1
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 5 ms 896 KB Output is correct
3 Correct 13 ms 2176 KB Output is correct
4 Correct 17 ms 2688 KB Output is correct
5 Correct 25 ms 3328 KB Output is correct
6 Correct 20 ms 3200 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 5 ms 1024 KB Output is correct
10 Correct 17 ms 2816 KB Output is correct
11 Correct 21 ms 3320 KB Output is correct
12 Correct 20 ms 3328 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 2 ms 512 KB Output is correct