oj.uz

Submission #209338

# Submission time Handle Problem Language Result Execution time Memory
209338 2020-03-13T20:14:35 Z papa Političari (COCI20_politicari) C++14
70 / 70
 53 ms 3064 KB 
#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

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.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 9 ms 1400 KB Output is correct
3 Correct 18 ms 2296 KB Output is correct
4 Correct 22 ms 2656 KB Output is correct
5 Correct 26 ms 2940 KB Output is correct
6 Correct 26 ms 2808 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 6 ms 888 KB Output is correct
9 Correct 10 ms 1528 KB Output is correct
10 Correct 53 ms 2552 KB Output is correct
11 Correct 26 ms 3064 KB Output is correct
12 Correct 26 ms 3064 KB Output is correct
13 Correct 5 ms 504 KB Output is correct
14 Correct 6 ms 888 KB Output is correct