Submission #581812

#	Time	Username	Problem	Language	Result	Execution time	Memory
581812		Josia	Game (IOI14_game)	C++14	0 / 100	1 ms	212 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) {
    if (find(a) == find(b)) return;

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

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

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


int hasEdge(int u, int v) {
    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: 0 / 15
• Subtask 2: 0 / 27
• Subtask 3: 0 / 58