Submission #669653

#	Time	Username	Problem	Language	Result	Execution time	Memory
669653		Marceantasy	Game (APIO22_game)	C++17	0 / 100	4 ms	7636 KiB

game

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long 
#define ar array
 
const int mxN = 3e5+5, M = 1e9+7; 
bool vis[mxN];
vector<int> adj[mxN];
int ans = 0;
int k, n;

void init(int n_, int k_){
    n = n_; 
    k = k_;
    memset(vis, 0, sizeof(vis));
    for(int i = 0; i<k; ++i){
        vis[i] = true;
        if(i < k-1){
            adj[i].push_back(i+1);
        }
    }
}

void dfs(int u){
    vis[u] = true;
    if(u < k){
        ans = 1;
        return;
    }
    for(int v : adj[u]){
        if(!vis[v]){
            dfs(v);
        }else if(vis[v] && v < k){
            ans = 1;
            return;
        }
    }
}

int add_teleporter(int u, int v){
    adj[u].push_back(v);
    if(vis[v] && vis[u] && v < k){

        ans = 1;
    }
    if(!vis[v] && vis[u]){
        dfs(v);
    }
    return ans;
}
/*
 
int main(){
#ifdef _DEBUG
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
    std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
 
    int N, K; 
    cin >> N >> K; 
    init(N, K);
    cout << add_teleporter(1, 1) << "\n";
    
    for(int i = 0; i<6; ++i){
        cout << i << " : " << vis[i] << "\n";
    }
    
}
*/

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