Submission #346432

#	Time	Username	Problem	Language	Result	Execution time	Memory
346432		Pichon5	Političari (COCI20_politicari)	C++17	45 / 70	58 ms	2540 KiB

politicari

#include<bits/stdc++.h>
#define lcm(a,b) (a/__gcd(a,b))*b
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define F first
#define S second
#define mp make_pair
//salida rapida "\n"
//DECIMALES fixed<<sp(n)<<x<<endl;
//gcd(a,b)= ax + by
//lCB x&-x
//set.erase(it) - ersases the element present at the required index//auto it = s.find(element)
//set.find(element) - iterator pointing to the given element if it is present else return pointer pointing to set.end()
//set.lower_bound(element) - iterator pointing to element greater than or equal to the given element
//set.upper_bound(element) - iterator pointing to element greater than the given element
// | ^
//stoll string to long long
using namespace std;
bool vis[501][501];
int M[501][501];
void init(){
    for(int i=0;i<501;i++){
        for(int l=0;l<501;l++){
            vis[i][l]=false;
        }
    }
}
int main()
{
    init();
    vi res      ;
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        for(int l=1;l<=n;l++){
            cin>>M[i][l];
        }
    }
    if(k==1){
        cout<<1<<endl;
        return 0;
    }
    int ant=1,curr=2;
    res.pb(1);
    vi res2;
    int c=1;
    while(1){
        c++;
        if(c==k){
            cout<<curr<<endl;
            return 0;
        }
        res.pb(curr);
        vis[ant][curr]=true;
        if(vis[curr][M[curr][ant]]==true){
            int a=curr;
            curr=M[curr][ant];
            ant=a;
            init();
            while(1){
                res2.pb(curr);
                vis[ant][curr]=true;
                if(vis[curr][M[curr][ant]]){
                    break;
                }
                a=curr;
                curr=M[curr][ant];
                ant=a;
            }
            break;
        }
        int aux=curr;
        curr=M[curr][ant];
        ant=aux;
    }
    k-=res.size();
    if(k<=res2.size()){
        cout<<res2[k-1]<<endl;
        return 0;
    }
    if(k%res2.size()==0){
        cout<<res2[res2.size()-1]<<endl;
        return 0;
    }
    cout<<res2[k%res2.size()-1]<<endl;


    return 0;
}

Compilation message (stderr)

politicari.cpp: In function 'int main()':
politicari.cpp:80:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     if(k<=res2.size()){
      |        ~^~~~~~~~~~~~~

• Subtask 1: 45 / 70