Submission #398784

#	Time	Username	Problem	Language	Result	Execution time	Memory
398784		faresbasbs	Cop and Robber (BOI14_coprobber)	C++14	16 / 100	66 ms	1716 KiB

coprobber

#include <bits/stdc++.h>
#include "coprobber.h"
using namespace std;
int n,curr,h[501],out[501],in[501];
vector<int> graph[501];
bool bad,seen[501];

void dfs(int curr , int par , int hi){
	h[curr] = hi;
	for(auto i : graph[curr]){
		if(i == par){
			continue;
		}
		if(!h[i]){
			dfs(i,curr,hi+1);
			continue;
		}
		if(h[i] < h[curr]){
			out[curr] += 1 , in[i] += 1;
			if(abs(h[i]-h[curr]) > 2){
				bad = 1;
			}
			continue;
		}
	}
	for(auto i : graph[curr]){
		if(h[i] < h[curr]){
			continue;
		}
		if(out[i] && out[curr]){
			bad = 1;
		}
	}
}

int start(int N , bool grid[MAX_N][MAX_N]){
	n = N;
	for(int i = 0 ; i < n ; i += 1){
		for(int j = 0 ; j < n ; j += 1){
			if(grid[i][j]){
				graph[i].push_back(j);
			}
		}
	}
	dfs(0,0,1);
	if(bad){
		return -1;
	}
	return 0;
}

bool fnd(int pos , int tar){
	seen[pos] = 1;
	if(pos == tar){
		return true;
	}
	for(auto i : graph[pos]){
		if(!seen[i] && fnd(i,tar)){
			return true;
		}
	}
	return false;
}

int nextMove(int r){
	memset(seen,0,sizeof seen);
	seen[curr] = 1;
	for(int i : graph[curr]){
		if(fnd(i,r)){
			return curr = i;
		}
	}
}

Compilation message (stderr)

coprobber.cpp: In function 'int nextMove(int)':
coprobber.cpp:73:1: warning: control reaches end of non-void function [-Wreturn-type]
   73 | }
      | ^

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