Submission #279669

#	Time	Username	Problem	Language	Result	Execution time	Memory
279669		PedroBigMan	Političari (COCI20_politicari)	C++14	70 / 70	25 ms	3328 KiB

politicari

#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 / 70