Submission #1275458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275458		pvpro	Game (APIO22_game)	C++20	2 / 100	1 ms	404 KiB

game

#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <chrono>
#include <random>
#include <complex>
#include <numeric>
#include <assert.h>
#include <functional>
#include <climits>
#include <cstring>
#include <iterator>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using ushort = unsigned short;

#ifndef LOCAL
#define endl "\n"
#endif
#define f first
#define s second
#define vec vector
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
template<typename T1, typename T2>
istream& operator>> (istream &in, pair<T1, T2> &p) { in >> p.f >> p.s; return in; }
template<typename T1, typename T2>
ostream& operator<< (ostream &out, pair<T1, T2> p) { out << "(" << p.f << " " << p.s << ")"; return out; }
#define printv(v) cerr << #v << " "; for (auto &x : v) { cerr << x << " "; } cerr << endl;
#define printvv(v) cerr << #v << " "; for (auto &x : v) { for (auto &y : x) { cerr << y << " "; } cerr << endl; }
#define debug(x) cerr << #x << " " << x << endl;

template<typename T>
istream& operator>> (istream &in, vector<T> &v) {
    for (auto &x : v) {
        in >> x;
    }
    return in;
}
template<typename T>
ostream& operator<< (ostream &out, vector<T> v) {
    for (auto &x : v) {
        out << x << " ";
    }
    return out;
}
template<typename T>
void operator-=(vector<T> &v, int delta) {
    for (auto &x : v) {
        x -= delta;
    }
}
template<typename T>
void operator+=(vector<T> &v, int delta) {
    for (auto &x : v) {
        x += delta;
    }
}

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

vector<vector<int>> graph, rgraph;
bool answer;
vector<int> l, r, nl, nr;
int K;

void init(int n, int k) {
    l.assign(n, 0);
    r.assign(n, k + 1);
    nl.assign(n, 0);
    nr.assign(n, k + 1);

    K = k;
    graph.assign(n, {});
    rgraph.assign(n, {});
    answer = false;
    for (int i = 0; i < k; ++i) {
        l[i] = i + 1;
        r[i] = i + 1;
        nl[i] = i + 1;
        nr[i] = i + 1;
    }
}

void update(int v) {
    if (v < K) {
        return;
    }
    if (answer) {
        return;
    }
    int m = (l[v] + r[v]) / 2;
    if (nl[v] > m || nr[v] <= m) {
        l[v] = nl[v];
        r[v] = nr[v];
        if (l[v] >= r[v]) {
            answer = true;
        }
        for (auto &u : graph[v]) {
            nl[u] = max(nl[u], l[v]);
            update(u);
        }
        for (auto &u : rgraph[v]) {
            nr[u] = min(nr[u], r[v]);
            update(u);
        }
    }
}

int add_teleporter(int a, int b) {
    if (answer) {
        return true;
    }
    if (a < K && b < K) {
        if (a >= b) {
            answer = true;
            return true;
        }
    }
    graph[a].pb(b);
    rgraph[b].pb(a);
    if (b >= K) {
        if (nl[b] < nl[a]) {
            nl[b] = nl[a];
            update(b);
        }
    }
    if (a >= K) {
        if (nr[a] > nr[b]) {
            nr[a] = nr[b];
            update(a);
        }
    }
    return answer;
}

#ifdef LOCAL
namespace {

    int read_int() {
        int x;
        if (scanf("%d", &x) != 1) {
            fprintf(stderr, "Error while reading input\n");
            exit(1);
        }
        return x;
    }

}  // namespace

int main() {
    freopen("in.txt", "r", stdin);
    int N = read_int();
    int M = read_int();
    int K = read_int();
    std::vector<int> u(M), v(M);
    for (int i = 0; i < M; ++i) {
        u[i] = read_int();
        v[i] = read_int();
    }

    init(N, K);
    int i;
    for (i = 0; i < M; ++i) {
        int answer = add_teleporter(u[i], v[i]);
        if (answer != 0 && answer != 1) {
            i = -1;
            break;
        } else if (answer == 1) {
            break;
        }
    }
    printf("%d\n", i);
    return 0;
}

#endif

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