oj.uz

Submission #861419

# Submission time Handle Problem Language Result Execution time Memory
861419 2023-10-16T06:48:26 Z Ellinor Cop and Robber (BOI14_coprobber) C++14
16 / 100
 57 ms 16528 KB 
#include "coprobber.h"

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
#pragma GCC optimize ("unroll-loops")

#pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
#pragma GCC target("movbe")                                      // byte swap
#pragma GCC target("aes,pclmul,rdrnd")                           // encryption
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")

typedef long long ll;
#define rep(i, a, b) for (int i = (a); i < int(b); i++)
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define pb push_back

// inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

ll INF = 1e15;
ll mod = 1e9 + 7;

// #define int ll
#define float double

int n;
vector<vector<int>> adj;
int cat = -1;

vector<vector<vector<pii>>> dp;
queue<array<int, 3>> q;

vector<vector<int>> r_edges_left;

void sol(int C, int R, int T)
{
    if (C == R) {
        dp[C][R][T].first = 1;
    }
    
    if (T == 1) {
        for (int i : adj[R]) {
            r_edges_left[C][i]--;
            if (r_edges_left[C][i] == 0) {
                q.push({C, i, 0});
            }
        }
    }

    else if (T == 0) {
        if (dp[C][R][1].first == -1) {
            q.push({C, R, 1});
        }
        // if (C != R) {
        //     for (int i : adj[R]) {
        //         if (dp[C][i][1].first != 1) {
        //             dp[C][R][0].first = 0;
        //             return;
        //         }
        //     }
        // }
        dp[C][R][0].first = 1;
        for (int i : adj[C]) {
            if (dp[i][R][1].first == -1) {
                dp[i][R][1].first = 1;
                dp[i][R][1].second = C;
                q.push({i, R, 1});
            }
        }
    }
}


int start(int N, bool A[MAX_N][MAX_N])
{
    n = N;
    adj.assign(n, {});
    rep(i,0,n) {
        rep(j,i + 1,n) {
            if (A[i][j]) {
                adj[i].pb(j);
                adj[j].pb(i);
            }
        }
    }

    dp.assign(n, vector<vector<pii>>(n, vector<pii>(2, {-1, -1})));
    rep(i,0,n) {
        q.push({i, i, 0});
        q.push({i, i, 1});
    }

    r_edges_left.assign(n, vector<int>(n, -1));
    rep(i,0,n) {
        rep(j,0,n) {
            r_edges_left[i][j] = adj[j].size();
        }
    }

    while (!q.empty()) {
        auto x = q.front();
        q.pop();
        sol(x[0], x[1], x[2]);
    }

    // rep(i,0,n) {
    //     rep(j,0,n) {
    //         rep(k,0,2) {
    //             cerr << dp[i][j][k].first << " ";
    //         }
    //         cerr << endl;
    //     }
    //     cerr << endl;
    // }

    rep(i,0,n) {
        bool w = true;
        rep(j,0,n) {
            if (dp[i][j][1].first != 1) w = false;
        }
        if (w) {
            return cat = i;
        }
    }

    return -1;
}

int nextMove(int R)
{
    if (cat == R) return cat; //
    return cat = dp[cat][R][1].second;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 47 ms 16412 KB Output is correct
5 Correct 12 ms 4440 KB Output is correct
6 Correct 57 ms 16528 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB the situation repeated
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 0 ms 344 KB the situation repeated
5 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 47 ms 16412 KB Output is correct
5 Correct 12 ms 4440 KB Output is correct
6 Correct 57 ms 16528 KB Output is correct
7 Incorrect 0 ms 344 KB the situation repeated
8 Halted 0 ms 0 KB -