oj.uz

답안 #100385

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
100385 2019-03-10T20:24:09 Z luciocf 게임 (IOI14_game) C++14
0 / 100
 3 ms 384 KB 
#include <bits/stdc++.h>
#include "game.h"

using namespace std;

const int maxn = 1510;

typedef pair<int, int> pii;

int pai[maxn], peso[maxn];
int cc;

set<pii> relation;

int Find(int x)
{
	if (pai[x] == x) return x;
	return pai[x] = Find(pai[x]);
}

void Join(int x, int y)
{
	x = Find(x), y = Find(y);
	if (x == y) return;

	if (peso[x] < peso[y]) swap(x, y);

	pai[y] = x, peso[x] += peso[y];
}

void initialize(int n) 
{
	cc = n;
	for (int i = 0; i < n; i++) pai[i] = i;

	for (int i = 0; i < n; i++)
		for (int j = i+1; j < n; j++)
			relation.insert({i, j});
}

int hasEdge(int u, int v) 
{
	if (Find(u) == Find(v)) return 1;
	if (cc == 2) return 0;

	int cu = Find(u), cv = Find(v);

	for (auto E: relation)
	{
		int a = E.first, b = E.second;
		int ca = Find(a), cb = Find(b);

		if ((a == u && b == v) || (a == v && b == u)) continue;

		if ((ca == cu && cb == cv || ca == cv && cb == cu))
		{
			if (relation.find({a, b}) != relation.end()) relation.erase({a, b});
			if (relation.find({b, a}) != relation.end()) relation.erase({b, a});

			return 0;
		}
	}

	if (relation.find({u, v}) != relation.end()) relation.erase({u, v});
	if (relation.find({v, u}) != relation.end()) relation.erase({v, u});

	Join(u, v);
	cc--;

	return 1;
}

Compilation message

game.cpp: In function 'int hasEdge(int, int)':
game.cpp:55:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if ((ca == cu && cb == cv || ca == cv && cb == cu))
        ~~~~~~~~~^~~~~~~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 58.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -