Submission #1296462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296462		eri16	Game (APIO22_game)	C++20	12 / 100	1 ms	464 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;

vector <int> vis;

int kk;

vector<vector<int>> adj;

void init(int n, int k){
    
    adj.assign(n, {});
    
    kk=k;
    
    vis.resize(n);
    
    for (int i=0; i<k; i++){
        vis[i]=k-i;
        if (i+1<k){adj[i].push_back(i+1);}
    }
    for (int i=k; i<n; i++){
        vis[i]=k+1;
    }
}

void dfs(int node,int color){
    vis[node]=color;
    for (int i=0; i<adj[node].size(); i++){
        if (vis[adj[node][i]]>color){
            dfs(adj[node][i],color);
        }
        if (kk-color==adj[node][i]){
            vis[kk-color]=0;    
        }
    }
}

int add_teleporter(int u, int v){
    
    adj[u].push_back(v);
    
    if (u==v){return 1;}
    
    if (vis[u]<vis[v]){
        dfs(v,vis[u]);
    }
    
    for (int i=0; i<kk; i++){
        if (vis[i]<kk-i){return 1;}
    }
    return 0;
}

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