Submission #852940

#	Time	Username	Problem	Language	Result	Execution time	Memory
852940		lovrot	Cop and Robber (BOI14_coprobber)	C++17	100 / 100	335 ms	10528 KiB

coprobber

#include <iostream>
#include <cstdio> 
#include <vector> 
#include <queue> 
#include "coprobber.h" 

#define EB emplace_back
#define MAX_N 500

using namespace std;

const int N = 510; 

struct node {
	int u, v, f;
	node() {}
	node(int u, int v, int f) : u(u), v(v), f(f) {}
};

int n;
vector<int> G[N], GP[N];

int CNT[N][N][2], NXT[N][N];
bool W[N][N][2];
queue<node> Q;

int pol = -1;

int start(int size, bool A[MAX_N][MAX_N]) {
	n = size;
	for(int u = 0; u < n; ++u) 
		for(int v = 0; v < n; ++v) {
			if(A[u][v]) {
				G[u].EB(v);
				GP[u].EB(v);
			} else if(u == v) { GP[u].EB(u); }
		}

//	printf("yes\n");

	for(int u = 0; u < n; ++u) {
		W[u][u][1] = 1;
		Q.push(node(u, u, 1));
	}
	
	while(!Q.empty()) {
		node s = Q.front(); 
		Q.pop();
		int u = s.u, v = s.v, f = s.f;
		if(f == 0) {
			for(int w : G[v]) {	
				++CNT[u][w][1];
				if(CNT[u][w][1] == G[w].size()) {
					W[u][w][1] = 1;
					Q.push(node(u, w, 1));
				}
			}
		} else {
			for(int w : GP[u]) 
				if(!W[w][v][0]) {
					W[w][v][0] = 1;
					NXT[w][v] = u;
					Q.push(node(w, v, 0)); 
				}
		}
	}

	for(int u = 0; u < n; ++u) {
		int cnt = 0;
		for(int v = 0; v < n; ++v) cnt += W[u][v][0];
		if(cnt == n) return pol = u;
	}
	return -1;
}

int nextMove(int R) {
	return pol = NXT[pol][R];
}
/*
// don't modify the main function
int main() {
    int N;
    cin >> N;
    bool A[MAX_N][MAX_N];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
        }
    }
    int P = start(N,A);
    cout << P << endl;
    int R;
    cin >> R;
    while (true) {
        if (P == R) break;
        P = nextMove(R);
        cout << P << endl;
        if (P == R) break;
        cin >> R;
    }
	return 0;
}
*/

Compilation message (stderr)

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:53:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     if(CNT[u][w][1] == G[w].size()) {
      |        ~~~~~~~~~~~~~^~~~~~~~~~~~~~

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