Submission #118662

#	Time	Username	Problem	Language	Result	Execution time	Memory
118662		onjo0127	Cop and Robber (BOI14_coprobber)	C++11	Compilation error	0 ms	0 KiB

coprobber

//*
//{
	#include <cstdio>
	#include <utility>
	using namespace std;

	const int MAX_N = 500;

	int start(int N, bool A[MAX_N][MAX_N]);
	int nextMove(int R);

	static const bool TRACK_CALLS = false;

	static int N, CopCanWin;
	static bool A[MAX_N][MAX_N];

	// Where should the robber go if the first index is the cop's
	// position and the second index is the robber's position?
	// RS[c][N] stores robber's starting corners.
	static int RobberStrategy[MAX_N][MAX_N + 1];

	// Visited positions are stored in the following array
	static bool VisitedPositions[MAX_N][MAX_N];

	static const int OK = 0, PARTFAIL = 1, FAIL = 2;
	static const char* Messages[] = { "OK", "PARTFAIL", "FAIL" };
	typedef pair<int, const char*> GraderResult;

	static GraderResult runGrader() {
	    int copCorner = start(N, A);
	    if (TRACK_CALLS)
	        fprintf(stderr, "start() = %d\n", copCorner);
	    
	    if ((copCorner != -1) && !CopCanWin)
	        return GraderResult(FAIL, "Cop cannot catch the robber, but start() did not return -1");
	    if ((copCorner == -1) && CopCanWin)
	        return GraderResult(FAIL, "Cop can catch the robber, but start() returned -1");
	    if (!CopCanWin)
	        return GraderResult(OK, NULL);
	    if (copCorner < 0 || copCorner >= N)
	        return GraderResult(FAIL, "start() returned a value that is outside the 0..N-1 range");
	    int robberCorner = RobberStrategy[copCorner][N];
	    
	    if (robberCorner == copCorner)  // If N = 1
	        return GraderResult(OK, NULL);
	    
	    while (true) {
	        int nextCopCorner = nextMove(robberCorner);
	        
	        if (TRACK_CALLS)
	            fprintf(stderr, "nextMove(%d) = %d\n", robberCorner, nextCopCorner);
	        

	        if (nextCopCorner < 0 || nextCopCorner >= N
	                || !(copCorner == nextCopCorner || A[copCorner][nextCopCorner]))
	            return GraderResult(PARTFAIL,
	                    "nextMove() returned a value that is either outside 0..N-1 "
	                    "or the new cop position is not a neighbour to the previous one");
	        copCorner = nextCopCorner;
	        
	        // Check if the same position has not been encountered before
	        if (VisitedPositions[copCorner][robberCorner])
	            return GraderResult(PARTFAIL, "the situation repeated");
	        VisitedPositions[copCorner][robberCorner] = true;
	        
	        // Check the winning condition
	        if (copCorner == robberCorner)
	            return GraderResult(OK, NULL);
	        
	        robberCorner = RobberStrategy[copCorner][robberCorner];
	        
	        // Moving to cop's position could have been the only
	        // valid move for the robber
	        if (copCorner == robberCorner)
	            return GraderResult(OK, NULL);
	    }
	}

	int main() {
	    scanf("%d", &N);
	    for (int i = 0; i < N; i++)
	        for (int j = 0; j < N; j++) {
	            int t;
	            scanf("%d", &t);
	            A[i][j] = t;
	        }
	    
	    scanf("%d", &CopCanWin);
	    if (CopCanWin) {
	        for (int c = 0; c < N; c++)
	            for (int r = 0; r <= N; r++)
	                scanf("%d", &RobberStrategy[c][r]);
	    }
	    
	    GraderResult result = runGrader();
	    puts(Messages[result.first]);
	    if (result.second != NULL)
	        puts(result.second);
	    
	    return 0;
	}
//}
//*/
//#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;

int now, n, D[MAX_N][MAX_N][2], deg[MAX_N][MAX_N], p = -1;
bool adj[MAX_N][MAX_N], vs[MAX_N][MAX_N];

void go(int c, int r, int t) {
	if(D[c][r][t] == 0) return;
	if(c != r && t == 1 && --deg[c][r] > 0) return;
	D[c][r][t] = 0;
	if(t == 0) {
		for(int i=0; i<n; i++) {
			if(adj[r][i]) go(c, i, 1);
		}
	}
	else {
		go(c, r, 0);
		for(int i=0; i<n; i++) {
			if(adj[c][i]) go(i, r, 0);
		}
	}
}

int start(int N, bool A[MAX_N][MAX_N]) {
	n = N;
	for(int i=0; i<n; i++) for(int j=0; j<n; j++) D[i][j][0] = D[i][j][1] = 1;
	for(int i=0; i<n; i++) for(int j=0; j<n; j++) adj[i][j] = A[i][j], deg[0][i] += A[i][j];
	for(int i=1; i<n; i++) for(int j=0; j<n; j++) deg[i][j] = deg[0][j];
	for(int i=0; i<n; i++) {go(i, i, 0); go(i, i, 1);}
	for(int i=0; i<n; i++) {
		bool fl = 1;
		for(int j=0; j<n; j++) if(D[i][j][0] == 1) fl = 0;
		if(fl) {
			return now = i;
		}
	}
	return -1;
}

bool chk(int v, int R) {
	for(int i=0; i<n; i++) if(A[R][i] && vs[v][i]) return 0;
	return 1;
}

int nextMove(int R) {
	vs[now][R] = 1;
	if(D[now][R][1] == 0 && chk(now, R)) return now;
	for(int i=0; i<n; i++) {
		if(adj[now][i] && D[i][R][1] == 0 && chk(i, R)) return i;
	}
	return -1;
}

Compilation message (stderr)

coprobber.cpp: In function 'int main()':
coprobber.cpp:80:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d", &N);
      ~~~~~^~~~~~~~~~
coprobber.cpp:84:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
              scanf("%d", &t);
              ~~~~~^~~~~~~~~~
coprobber.cpp:88:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d", &CopCanWin);
      ~~~~~^~~~~~~~~~~~~~~~~~
coprobber.cpp:92:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                  scanf("%d", &RobberStrategy[c][r]);
                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/tmp/ccR3cx88.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccl8u0xq.o:coprobber.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status