oj.uz

답안 #648220

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
648220 2022-10-05T17:47:55 Z Ronin13 경찰관과 강도 (BOI14_coprobber) C++14
0 / 100
 1 ms 336 KB 
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;

#define MAX_N 500

// modify the following functions
// you can define global variables and functions

bool dp[MAX_N][MAX_N][2];
bool used[MAX_N][MAX_N][2];
vector <vector <int> > grev(MAX_N);
int deg[MAX_N][MAX_N][2];
int cur;


void dfs(int v, int u, int ind){
    used[v][u][ind] = true;
    if(ind == 0){
        for(int to : grev[u]){
            if(used[v][to][ind ^ 1]) continue;
            if(dp[v][u][ind]){
                deg[v][to][ind ^ 1]--;
                if(deg[v][to][ind ^ 1] == 0) dp[v][to][ind ^ 1] = 0, dfs(v, to, ind ^ 1);
            }
            if(!dp[v][u][ind]) {
                dp[v][to][ind ^ 1] = true;
                dfs(v, to, ind ^ 1);
            }
        }

    }
    else{
       // grev[v].pb(v);
        for(int to : grev[v]){
            if(used[to][u][ind ^ 1]) continue;
            if(dp[v][u][ind]){
                deg[to][u][ind ^ 1]--;
                if(deg[to][u][ind ^ 1] == 0) dp[to][u][ind ^ 1] = 0, dfs(to, u, ind ^ 1);
            }
            if(!dp[v][u][ind]){
                dp[to][u][ind ^ 1] = true;
                dfs(to, u, ind ^ 1);
            }
        }
        if(used[v][u][ind ^ 1])return;
        if(dp[v][u][ind ^ 1]){
            deg[v][u][ind ^ 1]--;
            if(deg[v][u][ind ^ 1] == 0) dp[v][u][ind ^ 1] = 0, dfs(v, u, ind ^ 1);
        }
        else{
            dp[v][u][ind ^ 1] = 1;
            dfs(v, u, ind ^ 1);
        }
        //grev[v].pop_back();
    }
}



int start(int N, bool A[MAX_N][MAX_N]) {
    int n = N;
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			if(A[i][j]) grev[j].pb(i);
		}
	}
	for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            deg[i][j][0] = grev[j].size();
            deg[i][j][1] = grev[i].size() + 1;
        }
	}
	for(int i = 0; i < n; i++){
        dp[i][i][0] = 1;
        dp[i][i][1] = 0;
	}
	for(int i = 0; i < n; i++){
        dfs(i, i, 0);
        dfs(i, i, 1);
	}
    int ans = -1;
    for(int i = 0; i < n; i++){
        bool ind = true;
        for(int j= 0; j < n; j++){
            if(!dp[i][j][0]){
                ind = false;
                break;
            }
        }
        if(ind) {
            cur = i;
            return i;
        }
    }
    return -1;
}

int nextMove(int R) {
    for(int to : grev[cur]){
        if(dp[cur][R][1] == 0){
            return cur;
        }
        if(dp[to][R][1] == 0) {
            cur = to;
            return cur;
        }
    }
}

Compilation message

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:89:9: warning: unused variable 'ans' [-Wunused-variable]
   89 |     int ans = -1;
      |         ^~~
coprobber.cpp: In function 'int nextMove(int)':
coprobber.cpp:116:1: warning: control reaches end of non-void function [-Wreturn-type]
  116 | }
      | ^

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB Cop can catch the robber, but start() returned -1
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 336 KB Cop can catch the robber, but start() returned -1
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Incorrect 0 ms 336 KB Cop can catch the robber, but start() returned -1
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB Cop can catch the robber, but start() returned -1
4 Halted 0 ms 0 KB -