Submission #1051128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051128		TAhmed33	Game (IOI14_game)	C++98	0 / 100	0 ms	348 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int n;
set <int> dd[1502];
vector <vector <int>> comps;
void initialize (int N) {
    n = N;
  comps.clear();
  for (int i = 0; i < n; i++) dd[i].clear();
    for (int i = 0; i < n; i++) {
        comps.push_back({i});
    }
}
int id (int x) {
    int ii = -1;
    for (int j = 0; j < int(comps.size()); j++) {
        bool flag = 0;
        for (auto k : comps[j]) {
            if (k == x) {
                flag = 1;
                break;
            }
        }
        if (flag) {
            ii = j;
            break;
        }
    }
    return ii;
}
int get (int x) {
    int cnt = 0;
    for (auto j : comps[x]) {
        for (auto k : dd[j]) {
            if (id(k) != x) {
                cnt++;
            }
        }
    }
    return cnt;
}
int sze (int x) {
    return comps[x].size();
}
void merge (int x, int y) {
    for (auto j : comps[y]) {
        comps[x].push_back(j);
    }
    comps.erase(comps.begin() + y);
}
int hasEdge (int u, int v) {
    int ii = id(u), jj = id(v);
    assert(ii != jj);
    assert(ii != -1);
    assert(jj != -1);
    if (jj < ii) {
        swap(jj, ii);
        swap(u, v);
    }
    if (get(ii) == sze(ii) * (n - sze(ii)) - 1 || get(jj) == sze(jj) * (n - sze(jj)) - 1) {
        merge(ii, jj);
        return 1;
    }
    dd[u].insert(v); dd[v].insert(u);
    return 0;
}

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