Submission #1222928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222928		omsincoconut	게임 (APIO22_game)	C++17	0 / 100	0 ms	408 KiB

game

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

using namespace std;

namespace {
    int n, k;
    vector<vector<int>> edge, revedge;
    vector<int> maxin, minout;
}


void init(int _n, int _k) {
    n = _n, k = _k;
    edge = revedge = vector<vector<int>>(n);
    maxin = vector<int>(n, -1);
    minout = vector<int>(n, k+1);
}

bool return_value = false;

void propagate_max(int u) {
    for (int v : edge[u]) {
        if (maxin[v] < maxin[u]) {
            maxin[v] = maxin[u];
            if (maxin[v] >= minout[v]) return_value = true;
            propagate_max(v);
        }
    }
}

void propagate_min(int u) {
    for (int v : revedge[u]) {
        if (minout[v] > minout[u]) {
            minout[v] = minout[u];
            if (maxin[v] >= minout[v]) return_value = true;
            propagate_min(v);
        }
    }
}

int add_teleporter(int u, int v) {
    if (u < k && v < k) {
        if (v <= u) return 1;
        return 0;
    }

    edge[u].push_back(v);
    revedge[v].push_back(u);
    if (u < k) {
        maxin[v] = max(maxin[v], u);
    } else {
        maxin[v] = max(maxin[v], maxin[u]);
    }
    
    if (v < k) {
        minout[u] = min(minout[u], v);
    } else {
        minout[u] = min(minout[u], minout[v]);
    }

    propagate_min(u);
    propagate_max(v);

    if (maxin[u] >= minout[u]) return_value = true;
    if (maxin[v] >= minout[v]) return_value = true;
    
    return return_value;
}

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