oj.uz

Submission #710238

# Submission time Handle Problem Language Result Execution time Memory
710238 2023-03-15T05:58:51 Z Astrayt Game (APIO22_game) C++17
0 / 100
 4 ms 7248 KB 
#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[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;
        do{
            scc[cur] = 1;
            cnt += (cur < K);
            cur = stk.back(), stk.pop_back();
        }while(stk.size() && cur != u);
        if(!scc[u]){
            scc[cur] = 1;
            cnt += (cur < K);
        }
        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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7248 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7248 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7248 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7248 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7248 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -