Submission #860804

#	Time	Username	Problem	Language	Result	Execution time	Memory
860804		Ellinor	Cop and Robber (BOI14_coprobber)	C++14	16 / 100	165 ms	262144 KiB

coprobber

#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 pat = 0;

int dfs(int node, int par, int r)
{
    int ret = 0;
    if (node == r) ret = 1;

    rep(i,0,adj[node].size()) {
        if (adj[node][i] != par) {
            if (dfs(adj[node][i], node, r)) ret = adj[node][i];
        }
    }

    return ret;
}

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);
            }
        }
    }
    return 0;
}

int nextMove(int R)
{
    if (pat == R) exit(0);

    return pat = dfs(pat, -1, R);
}

// tree case

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