Submission #710252

#	Time	Username	Problem	Language	Result	Execution time	Memory
710252		Astrayt	Game (APIO22_game)	C++17	30 / 100	4014 ms	10304 KiB

game

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

int N, K, good = 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[v], low[u]);
        }else if(!scc[v]){
            low[u] = min(in[v], low[u]);
        }
    }
    if(low[u] >= in[u]){
        int cur = stk.back(), cnt = 0, cnt2 = 0;
        do{
            scc[cur] = 1;
            cnt += (cur < K);
            cnt2++;
            cur = stk.back(), stk.pop_back();
        }while(stk.size() && cur != u);
        if(!scc[u]){
            scc[cur] = 1;
            cnt += (cur < K);
            cnt2++;
        }
        if(cnt && cnt2 > 1) good = 1;
    }
}

int add_teleporter(int u, int v){
    if(u == v){
        if(u < K) return 1;
        else return 0;
    }
    adj[u].pb(v);
    good = 0, t = 1;
    in.assign(N, 0), low.assign(N, 0), scc.assign(N, 0);
    dfs(0);
    if(good) return 1;
    return 0;
}

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