Submission #581900

#	Time	Username	Problem	Language	Result	Execution time	Memory
581900		Josia	Game (IOI14_game)	C++14	100 / 100	503 ms	16468 KiB

game

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

using namespace std;

int N;

vector<pair<int, vector<int>>> chef;

void initUF() {
    chef.assign(N, {-1, vector<int>(N, 1)});
    for (int i = 0; i<N; i++) {
        chef[i].first = i;
    }
}

int find(int x) {
    if (chef[x].first == x) return x;
    return chef[x].first = find(chef[x].first);
}

void unite(int a, int b) {
    // cerr << "unite: " << find(a) << " " << find(b) << "\n";
    if (find(a) == find(b)) return;

    for (int i=0; i<N; i++)
        chef[find(b)].second[i] += chef[find(a)].second[i];

    for (int i = 0; i<N; i++)
        chef[find(i)].second[find(b)] = chef[find(b)].second[find(i)];
    chef[find(a)].first = find(b);
}

void initialize(int n) {
    N = n;
    initUF();
}


int hasEdge(int u, int v) {
    // cerr << u << " " << v << "\n";
    // for (auto i: chef) {
    //     for (int j: i.second) {
    //         cerr << j << " ";
    //     }
    //     cerr << "\n";
    // }
    // cerr << "\n\n";
    if (chef[find(u)].second[find(v)] == 1) {
        unite(u, v);
        return 1;
    }

    chef[find(u)].second[find(v)]--;
    chef[find(v)].second[find(u)]--;

    return 0;
}





void test(int n) {
    vector<pair<int, int>> edges;

    for (int i = 0; i<n; i++) {
        for (int j = i+1; j<n; j++) {
            edges.push_back({i, j});
        }
    }
    std::random_device rd;
    std::mt19937 g(rd());
    shuffle(edges.begin(), edges.end(), g);
    initialize(n);
    vector<int> answers;
    for (auto i: edges) {
        if (rand()%2==0) swap(i.first, i.second);
        cerr << i.first << " " << i.second << "\n";
        answers.push_back(hasEdge(i.first, i.second));
    }
    assert(answers.back() == 1);
    assert((int)accumulate(answers.begin(), answers.end(), 0) == (int)n-1);
}



// signed main() {
//     while (true) {
//         test(4);
//         cerr << "\n";
//     }
// }

• Subtask 1: 15 / 15
• Subtask 2: 27 / 27
• Subtask 3: 58 / 58