oj.uz

Submission #413555

# Submission time Handle Problem Language Result Execution time Memory
413555 2021-05-28T22:24:35 Z Blagojce Cop and Robber (BOI14_coprobber) C++11
60 / 100
 1500 ms 5560 KB 
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;
  
const int mxn = 505;


#include "coprobber.h"



int n;
vector<int> g[mxn];
vector<int> gc[mxn];

bool bad[mxn][mxn];
int nxt[mxn][mxn];

int cnt[mxn][mxn];


bitset<mxn> adj[mxn];
bitset<mxn> bit[mxn];


bool update_status(int u, int v){
	if(bit[u][v]) return false;
	
	for(auto e1 : gc[u]){
		if(cnt[e1][v] == (int)g[v].size()){
			nxt[u][v] = e1;
			bit[u][v] = 1;
			
			for(auto e2 : g[v]){
				cnt[u][e2] ++;
			}
			
			return true;
		}
	
	}
	return false;
	/*
	if(gc[u].size() >= sqrt(n)){
		for(auto e1 : gc[u]){
			bool ok = true;
			for(auto e2 : g[v]){
				ok &= bit[e1][e2];
			}
			if(ok){
				bit[u][v] = 1;
				nxt[u][v] = e1;
			}
		}
	}
	
	else{
		for(auto e1 : gc[u]){
			
			if((bit[e1]&adj[v]) == adj[v]){
				bit[u][v] = 1;
				nxt[u][v] = e1;
				return true;
			}
			
			bool ok = true;
			for(auto e2 : g[v]){
				ok &= bad[e1][e2];
			}
			bad[u][v] |= ok;
			if(ok){
				nxt[u][v] = e1;
				return true;
			}
		}
	}	
	return false;*/
}
int cop;

int start(int N, bool A[MAX_N][MAX_N])
{
	n = N;
	fr(i, 0, n){
		gc[i].pb(i);
		fr(j, 0, n){
			if(A[i][j]){
				adj[i][j] = 1;
				g[i].pb(j);
				gc[i].pb(j);
			}
		}
	}
	fr(i, 0, n){
		fr(j, 0, n){
			if(i == j){
				bit[i][j] = 1;
				nxt[i][j] = j;
			}
			else if(A[i][j]){
				bit[i][j] = 1;
				nxt[i][j] = j;
				for(auto e2 : g[j]){
					cnt[i][e2] ++;
				}
				
				
				//nxt[i][j] = j;
				
				//bad[i][j] = true;
			}
		}
	}
	bool progress = true;
	while(progress){
		progress = false;
		fr(i, 0, n){
			fr(j, 0, n){
				progress |= update_status(i, j);
			}
		}
	}
	fr(i, 0, n){
		bool cand = true;
		fr(j, 0, n){
			cand &= bit[i][j];
		}
		if(cand){
			cop = i;
			return i;
		}
	}
	return -1;
}
int nextMove(int R)
{	
	cop = nxt[cop][R];
	return cop;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 817 ms 3720 KB Output is correct
5 Correct 18 ms 1864 KB Output is correct
6 Correct 80 ms 3592 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 128 ms 3648 KB Output is correct
4 Correct 503 ms 3728 KB Output is correct
5 Correct 122 ms 3500 KB Output is correct
6 Correct 325 ms 3584 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 2 ms 712 KB Output is correct
11 Correct 3 ms 840 KB Output is correct
12 Correct 1 ms 456 KB Output is correct
13 Correct 2 ms 584 KB Output is correct
14 Correct 4 ms 744 KB Output is correct
15 Correct 2 ms 584 KB Output is correct
16 Correct 3 ms 584 KB Output is correct
17 Correct 6 ms 1096 KB Output is correct
18 Correct 2 ms 712 KB Output is correct
19 Correct 1 ms 328 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 817 ms 3720 KB Output is correct
5 Correct 18 ms 1864 KB Output is correct
6 Correct 80 ms 3592 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 128 ms 3648 KB Output is correct
10 Correct 503 ms 3728 KB Output is correct
11 Correct 122 ms 3500 KB Output is correct
12 Correct 325 ms 3584 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 1 ms 328 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 1 ms 328 KB Output is correct
19 Correct 1 ms 328 KB Output is correct
20 Correct 1 ms 328 KB Output is correct
21 Correct 1 ms 328 KB Output is correct
22 Correct 2 ms 712 KB Output is correct
23 Correct 3 ms 840 KB Output is correct
24 Correct 1 ms 456 KB Output is correct
25 Correct 2 ms 584 KB Output is correct
26 Correct 4 ms 744 KB Output is correct
27 Correct 2 ms 584 KB Output is correct
28 Correct 3 ms 584 KB Output is correct
29 Correct 6 ms 1096 KB Output is correct
30 Correct 2 ms 712 KB Output is correct
31 Correct 1 ms 328 KB Output is correct
32 Correct 1 ms 328 KB Output is correct
33 Correct 1 ms 328 KB Output is correct
34 Correct 1 ms 328 KB Output is correct
35 Correct 803 ms 3720 KB Output is correct
36 Correct 18 ms 1864 KB Output is correct
37 Correct 89 ms 3712 KB Output is correct
38 Correct 1 ms 328 KB Output is correct
39 Correct 1 ms 328 KB Output is correct
40 Correct 128 ms 3568 KB Output is correct
41 Correct 470 ms 3724 KB Output is correct
42 Correct 121 ms 3544 KB Output is correct
43 Correct 328 ms 3584 KB Output is correct
44 Correct 1 ms 328 KB Output is correct
45 Correct 1 ms 328 KB Output is correct
46 Correct 1 ms 328 KB Output is correct
47 Correct 1 ms 332 KB Output is correct
48 Correct 2 ms 712 KB Output is correct
49 Correct 3 ms 840 KB Output is correct
50 Correct 1 ms 456 KB Output is correct
51 Correct 2 ms 584 KB Output is correct
52 Correct 5 ms 712 KB Output is correct
53 Correct 2 ms 584 KB Output is correct
54 Correct 2 ms 584 KB Output is correct
55 Correct 6 ms 968 KB Output is correct
56 Correct 2 ms 712 KB Output is correct
57 Correct 6 ms 1224 KB Output is correct
58 Correct 20 ms 2120 KB Output is correct
59 Correct 40 ms 2572 KB Output is correct
60 Correct 482 ms 5520 KB Output is correct
61 Correct 114 ms 3292 KB Output is correct
62 Correct 109 ms 3612 KB Output is correct
63 Correct 1092 ms 5440 KB Output is correct
64 Correct 50 ms 2804 KB Output is correct
65 Execution timed out 1543 ms 5560 KB Time limit exceeded
66 Halted 0 ms 0 KB -