Submission #346536

#	Time	Username	Problem	Language	Result	Execution time	Memory
346536		saleh	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	679 ms	6796 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>

#define ft first
#define sd second

using namespace std;


typedef pair<int, int> pii;
typedef pair<int, pii> tip;

const int MAXN = 500 + 3;










int st, dd[MAXN], d[MAXN][MAXN], par[MAXN][MAXN];
queue<tip> q;
bitset<MAXN> mark[2 + 1][MAXN];



int start(int n, bool a[MAX_N][MAX_N]) {
	for (int i = 0; i < 2; i++) for (int j = 0; j < n; j++) {
		q.push({i, {j, j}});
		mark[i][j][j] = true;
	}
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dd[i] += a[i][j];
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) d[i][j] = dd[j];
	while (!q.empty()) {
		tip x = q.front();
		q.pop();
		if (x.ft == 0) {
			for (int i = 0; i < n; i++) if (a[i][x.sd.sd]) if (--d[x.sd.ft][i] == 0 && !mark[1][x.sd.ft][i]) {
				q.push({1, {x.sd.ft, i}});
				mark[1][x.sd.ft][i] = true;
			}
		} else {
			for (int i = 0; i < n; i++) if (i == x.sd.ft || a[i][x.sd.ft] == 1) if (!mark[0][i][x.sd.sd]) {
				q.push({0, {i, x.sd.sd}});
				par[i][x.sd.sd] = x.sd.ft;
				mark[0][i][x.sd.sd] = true;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		bool z = true;
		for (int j = 0; j < n; j++) z &= mark[0][i][j];
		if (z) return st = i;
	}
	return -1;
}
int nextMove(int r) {
	return st = par[st][r];
}

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