Submission #739140

#	Time	Username	Problem	Language	Result	Execution time	Memory
739140		PixelCat	Game (APIO22_game)	C++17	30 / 100	4 ms	464 KiB

game

#include "game.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define eb emplace_back
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 1010;

int n, k, ok;
vector<int> adj[MAXN], rev[MAXN];
int mx[MAXN]; // max special that can reach i
int mn[MAXN]; // min special that i can reach

void init(int _n, int _k) {
    n = _n; k = _k;
    ok = 0;
    For(i, 0, n - 1) {
        adj[i].clear();
        rev[i].clear();
        mx[i] = -1;
        mn[i] = n + 1;
    }
    For(i, 0, k - 2) {
        mx[i + 1] = i;
        mn[i] = i + 1;
        adj[i].eb(i + 1);
        rev[i + 1].eb(i);
    }
}

void dfs_mx(int x, int m) {
    if(mx[x] >= m) return;
    mx[x] = m;
    if(mx[x] >= mn[x]) {
        ok = 1; return;
    }
    for(auto &i:adj[x]) {
        dfs_mx(i, m);
    }
}

void dfs_mn(int x, int m) {
    if(mn[x] <= m) return;
    mn[x] = m;
    if(mx[x] >= mn[x]) {
        ok = 1; return;
    }
    for(auto &i:rev[x]) {
        dfs_mn(i, m);
    }
}

int add_teleporter(int u, int v) {
    if(u < k && v < k) {
        if(u >= v) return 1;
        return 0;
    }
    adj[u].eb(v);
    rev[v].eb(u);
    if(u < k) {
        dfs_mx(v, u);
        dfs_mn(u, mn[v]);
    } else if(v < k) {
        dfs_mx(v, mx[u]);
        dfs_mn(u, v);
    } else {
        dfs_mx(v, mx[u]);
        dfs_mn(u, mn[v]);
    }

    // cout << "mx:";
    // For(i, 0, n - 1) cout << " " << mx[i];
    // cout << "\n";
    // cout << "mn:";
    // For(i, 0, n - 1) cout << " " << mn[i];
    // cout << "\n";

    return ok;
}

/*

4
0
2

*/

• Subtask 1: 2 / 2
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 0 / 30
• Subtask 5: 0 / 40