Submission #209338

#	Time	Username	Problem	Language	Result	Execution time	Memory
209338		papa	Političari (COCI20_politicari)	C++14	70 / 70	53 ms	3064 KiB

politicari

#include <bits/stdc++.h>

using namespace std;

//radimo rucno dok ne naidjemo na par suseda na koje smo vec naisli 
//tada nadjemo prvo pojavljivanje njih i izmedju te dve pozicije ide ciklus 
//onda klasicno iz ciklusa izvucemo k-ti element pomocu % operacije 
//a ostatak rucno

int n;
vector<int> v;
long long k;
int a[505][505];
int p[505][505];

int pozicija(int x,int y)
{
    for(int i=0;i<v.size()-1;i++)
        if(v[i]==x && v[i+1]==y) return i;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cerr.tie(0);

    cin >> n >> k;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) cin >> a[i][j];

   if(k==1)
   {
       cout << 1;
       return 0;
   }

   if(k==2)
   {
       cout << 2;
       return 0;
   }

   v.push_back(1);
   v.push_back(2);
   p[1][2] = 1;
   int prv = 1;
   int temp = 2;
   long long tempk = k;
   tempk-=2;
   int ind = 1;
   while(tempk > 0)
   {
       ind++;
       int xx = temp;
       v.push_back(a[temp][prv]);
       temp = a[temp][prv];
       prv = xx;
       if(p[prv][temp])
       {
           //cout << "ovde";
           int pos = pozicija(prv,temp);
           int duz = ind - pos - 1;
           k = k - (ind-1);
           k = k%duz;
           if(k==0) cout << v[ind-2];
           else cout << v[pos+k-1];
           return 0;
       }
       p[prv][temp] = 1;
       //tempk=0;
       tempk--;
   }

  cout << v[v.size()-1];

   return 0;
}

Compilation message (stderr)

politicari.cpp: In function 'int pozicija(int, int)':
politicari.cpp:18:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v.size()-1;i++)
                 ~^~~~~~~~~~~
politicari.cpp:20:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 70 / 70