제출 #69499

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69499		E869120	게임 (IOI14_game)	C++14	0 / 100	3 ms	592 KiB

game

#include "game.h"
#include <vector>
using namespace std;

class MergeTech {
public:
	vector<int>group; vector<vector<int>>G, I; int sz = 0;

	void init(int size_) {
		sz = size_;
		group.resize(size_);
		G.resize(size_, vector<int>(0, 0));
		I.resize(size_, vector<int>(size_, 1));
		for (int i = 0; i < size_; i++) { G[i].push_back(i); group[i] = i; I[i][i] = 0; }
	}
	void unite(int u, int v) {
		u = group[u]; v = group[v];
		if (u == v) return;

		if (G[u].size() < G[v].size()) swap(u, v);

		for (int i = 0; i < G[v].size(); i++) { G[u].push_back(G[v][i]); group[G[v][i]] = u; }
		G[v].clear();
		for (int i = 0; i < sz; i++) { if (i != u && i != v) { I[u][i] += I[v][i]; I[v][i] = 0; } }
		for (int i = 0; i < sz; i++) { if (i != u && i != v) { I[i][u] += I[i][v]; I[i][v] = 0; } }
		I[u][v] = 0; I[v][u] = 0;
	}
	int query(int u, int v) {
		u = group[u]; v = group[v];
		if (u == v) return -1;
		return I[u][v];
	}
	void decrease(int u, int v) {
		u = group[u]; v = group[v];
		I[u][v]--;
	}
};

MergeTech UF;

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

int hasEdge(int u, int v) {
	if (UF.query(u, v) == 1) {
		UF.unite(u, v);
		return 1;
	}
	UF.decrease(u, v);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

game.cpp: In member function 'void MergeTech::unite(int, int)':
game.cpp:22:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < G[v].size(); i++) { G[u].push_back(G[v][i]); group[G[v][i]] = u; }
                   ~~^~~~~~~~~~~~~

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