Submission #393451

#	Time	Username	Problem	Language	Result	Execution time	Memory
393451		peuch	Game (IOI14_game)	C++17	100 / 100	597 ms	24780 KiB

game

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

const int MAXN = 1510;

int N;
int rep[MAXN], tam[MAXN];
vector<int> grp[MAXN];
int conect[MAXN][MAXN];

int find(int a){
	if(rep[a] == a) return a;
	return rep[a] = find(rep[a]);
}

bool test(int u, int v){
	u = find(u);
	v = find(v);
	if(rand() & 1) swap(u, v);
	conect[u][v]++;
	conect[v][u]++;
	int cnt = 0;
	for(int i = 0; i < grp[u].size(); i++)
		cnt += conect[v][grp[u][i]];
	return cnt == tam[u] * tam[v];
}

void uni(int a, int b){
	a = find(a);
	b = find(b);
	if(rand() & 1) swap(a, b);
	for(int i = 0; i < grp[a].size(); i++){
		grp[b].push_back(grp[a][i]);
	}
	for(int i = 0; i < N; i++)
		conect[b][i] += conect[a][i];
	rep[a] = b;
	tam[b] += tam[a];
}

void initialize(int n) {
	srand(time(0));
	N = n;
	for(int i = 0; i < N; i++){
		rep[i] = i;
		grp[i].push_back(i);
		tam[i] = 1;
	}
}

int hasEdge(int u, int v) {
	if(test(u, v)) {
		uni(u, v);
		return 1;
	}
    return 0;
}

Compilation message (stderr)

game.cpp: In function 'bool test(int, int)':
game.cpp:23:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for(int i = 0; i < grp[u].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~
game.cpp: In function 'void uni(int, int)':
game.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for(int i = 0; i < grp[a].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~

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