Submission #1003395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003395		mispertion	Game (APIO22_game)	C++17	2 / 100	13 ms	23920 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

#define pb(x) push_back(x);

const int N = 5e5;
const int infi = INT_MAX;

vector<int> g[N], ig[N];
int n, k, lf[N], rt[N];

bool add_edge(int u, int v);

bool upd_vert(int v){
    bool was = false;
    for(auto u : g[v]){
        if(add_edge(v, u))
            was = true;
    }
    for(auto u : ig[v]){
        if(add_edge(u, v))
            was = true;
    }
    return was;
}

bool add_edge(int u, int v){
    //u-->v
    if(rt[u] <= lf[v]){
        return false;
    }
    if(rt[v] <= lf[u])
        return true;
    if(lf[u] == lf[v] && rt[u] == rt[v])
        return false;
    if((lf[u] + rt[u]) / 2 >= rt[v]){
        rt[u] = (lf[u] + rt[u]) / 2;
        return upd_vert(u);
    }else if((lf[v] + rt[v]) / 2 <= lf[u]){
        lf[v] = (lf[v] + rt[v]) / 2;
        return upd_vert(v);
    }else{
        return false;
    }
}

void init(int _n, int _k) {
    n = _n;
    k = _k;
    for(int i = 1; i <= k; i++)
        lf[i] = i, rt[i] = i + 1;
    for(int i = k + 1; i <= n; i++)
        lf[i] = 0, rt[i] = k + 1;
}

int add_teleporter(int u, int v) {
    u++;
    v++;
    if(u == v && u <= k)
        return 1;
    if(u == v)
        return 0;
    g[u].pb(v);
    ig[v].pb(u);
    return add_edge(u, v);
}

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