Submission #887567

#	Time	Username	Problem	Language	Result	Execution time	Memory
887567		TahirAliyev	Game (IOI14_game)	C++17	42 / 100	1041 ms	6636 KiB

game

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

using namespace std;

#define pii pair<int, int>

const int MAX = 1505;

int N;
int par[MAX];
int c;

set<pii> edges;

int get(int node){
    if(par[node] < 0) return node;
    return get(par[node]);
}

stack<array<int, 4>> calls;

bool unite(int u, int v, bool isTemp){
    u = get(u);
    v = get(v);
    if(u == v) return 0;
    if(-par[u] < -par[v]) swap(u, v);
    if(isTemp){
        calls.push({u, v, par[u], par[v]});
    }
    par[u] += par[v];
    par[v] = u;
    c--;
    return 1;
}

void rollback(){
    while(calls.size()){
        auto a = calls.top();
        par[a[0]] = a[2];
        par[a[1]] = a[3];
        c++;
        calls.pop();
    }
}

void initialize(int n) {
    memset(par, -1, sizeof(par));
    N = n;
    c = n;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            edges.insert({i, j});
        }
    }
}

int hasEdge(int u, int v) {
    if(u > v) swap(u, v);
    edges.erase({u, v});

    if(edges.size() < c - 1){
        unite(u, v, 0);
        return 1;
    }
    for(auto a : edges){
        unite(a.first, a.second, 1);
    }
    if(c != 1){
        rollback();
        unite(u, v, 0);
        return 1;
    }
    rollback();
    return 0;
    
}

Compilation message (stderr)

game.cpp: In function 'int hasEdge(int, int)':
game.cpp:62:21: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |     if(edges.size() < c - 1){
      |        ~~~~~~~~~~~~~^~~~~~~

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