Submission #601286

#	Time	Username	Problem	Language	Result	Execution time	Memory
601286		doowey	Game (APIO22_game)	C++17	60 / 100	4103 ms	25020 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

int n, k;
const int N = (int)3e5 + 10;
int low[N];

void init(int _n, int _k) {
    n = _n;
    k = _k;
    for(int i = 0 ; i < n; i ++ ){
        low[i] = n + 1;
    }
}
vector<int> in[N];

bool sol = false;

void dfs(int u, int val){
    low[u]=val;
    if(u < k && low[u] <= u){
        sol = true;
    }
    if(sol) return;
    for(auto x : in[u]){
        if(low[x] > val){
            dfs(x, val);
        }
    }
}

int add_teleporter(int u, int v) {
    if(v < k){
        if(low[u] > v)
            dfs(u, v);
    }
    else{
        if(low[u] > low[v]){
            dfs(u, low[v]);
        }
    }
    in[v].push_back(u);
    return sol;
}

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