Submission #1126622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126622		Halym2007	Cop and Robber (BOI14_coprobber)	C++17	0 / 100	1 ms	328 KiB

coprobber

#include <bits/stdc++.h>
#include "coprobber.h"
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
#define dur exit(0)
#define dur1 return(0)
const int NN = 500;

bool a[NN][NN];
int n, cur, par = -1; 
vector <int> v[NN];

int start(int N, bool a[NN][NN]) {
    n = N;
    for (int i = 0; i < n; ++i) {
    	for (int j = 0; j < n; ++j) {
    		if (a[i][j]) {
    			v[i].pb (j);
				v[j].pb (i);
			}
		}
	}
	return 0;
}


int icindemi (int x, int par, int y) {
	int ret = 0;
	if (x == y) return 1;
	for (int i : v[x]) {
		if (i == par) continue;
		ret |= icindemi (i, x, y);
	}
	return ret;
}

int nextMove(int R) {
	for (int i : v[cur]) {
		if (icindemi(i, -1, R)) {
			cur = i;
			break;
		}
	}
    return cur;
}

/*

static const bool TRACK_CALLS = false;

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

// 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[NN][NN + 1];

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

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);
        
        /**
         * Check if the move is valid:
         *   - the returned corner is within bounds
         *   - the new corner is either the same or is a neighbour to the old one
         */
         /*
        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() {
	freopen ("input.txt", "r", stdin);
    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;
}
///*

4
0 1 1 1
1 0 0 0
1 0 0 0
1 0 0 0
1
0 0 0 0 1
2 0 0 0 2
1 0 0 0 1
1 0 0 0 1

*/

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