Submission #558128

#	Time	Username	Problem	Language	Result	Execution time	Memory
558128		Olympia	Game (IOI14_game)	C++17	0 / 100	1 ms	212 KiB

game

#include <bits/stdc++.h>
#include <game.h>
using namespace std;
struct dsu {
    vector<int> parent;
    vector<int> compSize;
    int n;
    int cc = 0;
    void fill(){
        cc = n;
        parent.resize(n), compSize.resize(n);
        for(int i = 0; i < n; i++){
            parent[i] = i, compSize[i] = 1;
        }
    }
    int find_head(int x){
        if(x == parent[x]){
            return x;
        }
        return find_head(parent[x]);
    }
    void join(int x, int y){
        cc--;
        x = find_head(x);
        y = find_head(y);
        if(x == y){
            return;
        }
        if(compSize[x] > compSize[y]){
            swap(x,y);
            //ensures that compSize[x1] <= compSize[y1]
        }
        parent[x] = y;
        compSize[y] += compSize[x]; 
    }
    bool comp(int x, int y){
        return (find_head(x) == find_head(y));
    }
};
dsu d;
vector<set<int> > e;
void initialize (int n)  {
    d.n = n;
    e.resize(n);
    d.fill();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (j != i) {
                e[i].insert(j);
            }
        }
    }
}
int hasEdge (int u, int v) {
    e[u].erase(v);
    e[v].erase(u);
    d.fill();
    for (int i = 0; i < e.size(); i++) {
        for (int j: e[i]) {
            d.join(i, j);
        }
    }
    if (d.cc != 1) {
        return false;
    }
    e[u].insert(v);
    e[v].insert(u);
    return true;
}

Compilation message (stderr)

game.cpp: In function 'int hasEdge(int, int)':
game.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::set<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (int i = 0; i < e.size(); i++) {
      |                     ~~^~~~~~~~~~

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