Submission #998737

#	Time	Username	Problem	Language	Result	Execution time	Memory
998737		Alfraganus	Game (IOI14_game)	C++17	100 / 100	241 ms	27220 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

struct DSU {

    vector<int> p, sz;
    vector<vector<int>> edges;

    void init(int n){
        p.resize(n);
        sz.resize(n);
        edges.resize(n, vector<int> (n, 1));
        for(int i = 0; i < n; i ++)
            p[i] = i, sz[i] = 1, edges[i][i] = 0;
    }

    void add(int a, int b){
        if(a == b)
            return;
        if(sz[a] < sz[b])
            swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
        for(int i = 0; i < p.size(); i ++){
            if(i != a)
                edges[a][i] += edges[b][i];
            edges[i][a] = edges[a][i];
        }
    }

    int find_parent(int n){
        if(n == p[n])
            return n;
        return p[n] = find_parent(p[n]);
    }
};

DSU d;

void initialize(int n) {
    d.init(n);
}

int hasEdge(int u, int v) {
    u = d.find_parent(u);
    v = d.find_parent(v);
    if(d.edges[u][v] == 1){
        d.add(u, v);
        d.edges[u][v] --;
        d.edges[v][u] --;
        return 1;
    }
    d.edges[u][v] --;
    d.edges[v][u] --;
    return 0;
}

Compilation message (stderr)

game.cpp: In member function 'void DSU::add(int, int)':
game.cpp:25:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for(int i = 0; i < p.size(); i ++){
      |                        ~~^~~~~~~~~~

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