Submission #1275367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275367		pvpro	Game (APIO22_game)	C++20	60 / 100	4016 ms	24048 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;
bool answer;
vector<int> d;
int K;

void init(int n, int k) {
    d.assign(n, -1);
    K = k;
    graph.assign(n, {});
    answer = false;
    for (int i = 0; i < k; ++i) {
        d[i] = i;
    }
}

void update(int v) {
    for (auto &u : graph[v]) {
        if (u <= d[v]) {
            answer = true;
        } else if (u >= K) {
            if (d[u] < d[v]) {
                d[u] = d[v];
                update(u);
            }
        }
    }
}

int add_teleporter(int a, int b) {
    if (answer) {
        return true;
    }
    graph[a].pb(b);
    if (b < K) {
        answer = (d[a] >= b);
    } else {
        if (d[b] < d[a]) {
            d[b] = d[a];
            update(b);
        }
    }
    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: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 30 / 30
• Subtask 5: 0 / 40