oj.uz

Submission #54993

# Submission time Handle Problem Language Result Execution time Memory
54993 2018-07-05T17:10:41 Z cki86201 Cop and Robber (BOI14_coprobber) C++11
16 / 100
 281 ms 11972 KB 
#include "coprobber.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>
#include <complex.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

int d[2][510][510], nxt[510][510], cnt[510][510];
int deg[510];
vector <t3> V;
int now_p;

int start(int N, bool A[MAX_N][MAX_N])
{
    rep(i, N) rep(j, N) deg[i] += A[i][j];
    rep(i, N) rep(k, 2) V.pb(t3(k, i, i)), d[k][i][i] = 1, nxt[i][i] = -1;
    rep(i,szz(V)) {
        int t, p, r;
        tie(t, p, r) = V[i];
        if(t == 0) {
            rep(j, N) if(A[r][j]) {
                if(d[1][p][j] == 0) {
                    cnt[p][j]++;
                    if(cnt[p][j] == deg[j]) {
                        d[1][p][j] = 1;
                        V.pb(t3(1, p, j));
                    }
                }
            }
        }
        else {
            rep(j, N) if(A[p][j]) {
                if(d[0][j][r] == 0) {
                    nxt[j][r] = p;
                    d[0][j][r] = 1;
                    V.pb(t3(0, j, r));
                }
            }
        }
    }
    rep(i, N) {
        int ok = 1;
        rep(j, N) if(d[0][i][j] == 0) { ok = 0; break; }
        if(ok) return now_p = i;
    }
    return -1;
}

int nextMove(int R)
{
    return now_p = nxt[now_p][R];
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 253 ms 11844 KB Output is correct
5 Correct 39 ms 4464 KB Output is correct
6 Correct 281 ms 11860 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Cop can catch the robber, but start() returned -1
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Incorrect 2 ms 384 KB Cop can catch the robber, but start() returned -1
5 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 246 ms 11972 KB Output is correct
5 Correct 39 ms 4464 KB Output is correct
6 Correct 281 ms 11896 KB Output is correct
7 Incorrect 2 ms 384 KB Cop can catch the robber, but start() returned -1
8 Halted 0 ms 0 KB -