Submission #727449

#	Time	Username	Problem	Language	Result	Execution time	Memory
727449		AdamGS	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	949 ms	8612 KiB

coprobber

#include "coprobber.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=507;
int dp[LIM][LIM][2], deg[LIM][LIM], lst[LIM][LIM], akt;
int start(int n, bool A[MAX_N][MAX_N]) {
	queue<pair<pair<int,int>,int>>q;
	rep(i, n) {
		dp[i][i][0]=dp[i][i][1]=1;
		q.push({{i, i}, 0});
		q.push({{i, i}, 1});
	}
	rep(i, n) rep(j, n) if(i!=j) {
		rep(l, n) if(A[j][l]) ++deg[i][j];
	}
	while(!q.empty()) {
		int a=q.front().st.st, b=q.front().st.nd, c=q.front().nd; q.pop();
		if(c==0) {
			rep(i, n) if(A[i][b] && !dp[a][i][1]) {
				--deg[a][i];
				if(!deg[a][i]) {
					dp[a][i][1]=1;
					q.push({{a, i}, 1});
				}
			}
		} else {
			if(!dp[a][b][0]) {
				dp[a][b][0]=1;
				lst[a][b]=a;
				q.push({{a, b}, 0});
			}
			rep(i, n) if(A[i][a] && !dp[i][b][0]) {
				dp[i][b][0]=1;
				lst[i][b]=a;
				q.push({{i, b}, 0});
			}
		}
	}
	rep(i, n) {
		bool ok=true;
		rep(j, n) ok&=dp[i][j][0];
		if(ok) {
			akt=i;
			return akt;
		}
	}
	return -1;
}
int nextMove(int R) {
	akt=lst[akt][R];
	return akt;
}

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