Submission #710204

#	Time	Username	Problem	Language	Result	Execution time	Memory
710204		Astrayt	Game (APIO22_game)	C++17	0 / 100	4 ms	7248 KiB

game

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define maxn 300005

int N, K, mxcnt = 0, t = 1;
vector<int> in, low, scc, stk, adj[maxn];

void init(int n, int k){
    N = n, K = k;
    for(int i = 0; i < k - 1; ++i) adj[i].pb(i + 1);
}

void dfs(int u){
    in[u] = low[u] = t++;
    stk.pb(u);
    for(int v:adj[u]){
        if(!in[v]){
            dfs(v);
            low[u] = min(low[u], low[v]);
        }else if(!scc[v]){
            low[u] = min(in[v], low[u]);
        }
    }
    if(low[u] == in[u]){
        int cur = stk.back(), cnt = 0;
        do{
            scc[cur] = 1;
            cnt += (cur < K);
            cur = stk.back(), stk.pop_back();
        }while(stk.size() && cur != u);
        mxcnt = max(mxcnt, cnt);
    }
}

int add_teleporter(int u, int v){
    adj[u].pb(v);
    mxcnt = 0, t = 1;
    in.assign(N, 0), low.assign(N, 0), scc.assign(N, 0);
    dfs(0);
    if(mxcnt >= 2) return 1;
    return 0;
}

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