Submission #752632

#	Time	Username	Problem	Language	Result	Execution time	Memory
752632		Dan4Life	Game (APIO22_game)	C++17	60 / 100	1035 ms	20940 KiB

game

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int mxN = (int)2e5+10;
int n, k, L[mxN], R[mxN];
vector<int> adj[mxN], radj[mxN];
 
void init(int N, int K) {
    n = N; k = K;
    for(int i = 0; i < k; i++) L[i]=R[i]=i;
    for(int i = k; i < n; i++) L[i]=n,R[i]=-1;
}
 
void dfs(int s, int c, vector<int> adj[], bool ok){ 
    if(ok){
        if(c<k and R[s]<c) R[s]=c;
        else return;
    }
    else{
        if(L[s]>c) L[s]=c; 
        else return;
    }
    for(auto u : adj[s]) dfs(u,c,adj,ok);
}
 
int add_teleporter(int u, int v) {
    if(u>=v and u<k) return 1;
    if(max(u,v)<k) return 0;
    adj[u].pb(v), radj[v].pb(u);
    dfs(u, L[v], radj,0), dfs(v,R[u], adj,1); 
    return (L[v]<=R[u] and R[u]<k);
}

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