Submission #248571

#	Time	Username	Problem	Language	Result	Execution time	Memory
248571		kshitij_sodani	Cop and Robber (BOI14_coprobber)	C++14	16 / 100	467 ms	62200 KiB

coprobber

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#include "coprobber.h"

//#define MAX_N 500

//#include "coprobber.h"
vector<int> adj[500*500*2];
vector<int> adj2[500*500*2];
int vis[500*500*2];
int back[500*500*2];

int co[500*500*2];
//i*j+n*n*k,k=0 if police,i police,j robber
int cur=0;
int n;
int start(int nn, bool aa[MAX_N][MAX_N]){
	n=nn;

	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			adj[i*n+j].pb(n*n+i*n+j);
			adj2[n*n+i*n+j].pb(n*n+i*n+j);
			for(int k=0;k<n;k++){
				if(aa[i][k]){
					adj[i*n+j].pb(k*n+j+n*n);
					adj2[k*n+j+n*n].pb(i*n+j);
				}
			}
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){			
			for(int k=0;k<n;k++){
				if(aa[j][k]){
					adj[i*n+j+n*n].pb(i*n+k);
					adj2[i*n+k].pb(i*n+j+n*n);
				}
			}
		}
	}
	queue<int> ss;
	for(int i=0;i<n;i++){
		vis[i*n+i]=1;
		ss.push(i*n+i);
		vis[n*n+i*n+i]=1;
		ss.push(n*n+i*n+i);
	}
	while(ss.size()){
		int no=ss.front();
		ss.pop();
		for(auto j:adj2[no]){
			if(vis[j]){
				continue;
			}
			if(j>=n*n){
				co[j]+=1;
				if(co[j]==adj[j].size()){
					vis[j]=1;
					ss.push(j);

				}
			}
			else{
				vis[j]=1;
				ss.push(j);
				back[j]=no;
			}
		}
	}


	for(int i=0;i<n;i++){
		int st=1;
		for(int j=0;j<n;j++){
			if(vis[i*n+j]==0){
				st=0;
			}
		}
		if(st){
			cur=i;
		//	cout<<i<<endl;
			return i;
		}
	}
	return -1;
}

int nextMove(int rr){
//	cout<<back[cur*n+rr]<<endl;
	cur=back[cur*n+rr]/n-n;

    return cur;
}

/*
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);


	return 0;
}*/

/*
g++  -o aa -O2 aa.cpp grader.cpp -std=c++14
*/

Compilation message (stderr)

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:63:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(co[j]==adj[j].size()){
        ~~~~~^~~~~~~~~~~~~~~

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