Submission #1053309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053309		user736482	Cop and Robber (BOI14_coprobber)	C++17	30 / 100	30 ms	1872 KiB

coprobber

#include<bits/stdc++.h>
#include<coprobber.h>
using namespace std;

vector<int> sasiad[507];
int akpos;
int licz,wym1,wym2;
int n,lastr=-1;

int to_pos(int x,int y){
    return y*wym1+x;
}
pair<int,int> to_coordinates(int val){
    return {val%wym1,val/wym1};
}

int start(int N,bool a[][500]){
    n=N;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(a[i][j]){
                sasiad[i].push_back(j);
                sasiad[j].push_back(i);
                licz++;
                if(i==0)
                    if(j!=1)
                        wym1=j;
                if(j==n)
                    if(i!=n-1)
                        wym2=n-i;
            }
        }
    }
    return 0;
}
int nextMove(int r){
    if(licz==n-1){
        bool odw[507];
        int pop[507];
        for(int i=0;i<507;i++)
            odw[i]=0;
        odw[akpos]=1;
        pop[akpos]=akpos;
        queue<int>q;
        q.push(akpos);
        while(!q.empty()){
            int pom=q.front();
            q.pop();
            for(int i=0;i<sasiad[pom].size();i++){
                if(!odw[sasiad[pom][i]]){
                    odw[sasiad[pom][i]]=1;
                    pop[sasiad[pom][i]]=pom;
                    q.push(sasiad[pom][i]);
                }
            }
        }
        while(pop[r]!=akpos)
            r=pop[r];
        akpos=r;
        return r;
    }
    int x1=to_coordinates(akpos).first;
    int y1=to_coordinates(akpos).second;
    int x2=to_coordinates(r).first;
    int y2=to_coordinates(r).second;
    if(abs(x1-x2)==abs(y1-y2))
        return akpos;
    if(abs(x1-x2)>abs(y1-y2))
        if(x1>x2)
            x1--;
        else
            x1++;
    else
        if(y1>y2)
            y1--;
        else
            y1++;
    akpos=to_pos(x1,y1);
    return akpos;
}

Compilation message (stderr)

coprobber.cpp: In function 'int nextMove(int)':
coprobber.cpp:49:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             for(int i=0;i<sasiad[pom].size();i++){
      |                         ~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 14 / 14
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40