oj.uz

Submission #727448

# Submission time Handle Problem Language Result Execution time Memory
727448 2023-04-20T17:11:41 Z AdamGS Cop and Robber (BOI14_coprobber) C++17
0 / 100
 1500 ms 336 KB 
#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[500][500]) {
	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;
		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
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3047 ms 300 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3051 ms 336 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3063 ms 208 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3047 ms 300 KB Time limit exceeded
2 Halted 0 ms 0 KB -