제출 #161938

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
161938		kostia244	Game (IOI14_game)	C++14	42 / 100	1075 ms	6580 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
struct dsu {
	vi r, p;
	void init(int n) {
		r.resize(n+1);
		p.resize(n+1);
		for(int i = 0; i <= n; i++) p[i] = i;
	}
	int par(int i) {
		if(i == p[i]) return i;
		return p[i] = par(p[i]);
	}
	void unite(int u, int v) {
		u=par(u),v=par(v);
		if(u==v) return;
		if(r[u]<r[v]) swap(u, v);
		p[v] = u;
		r[u] += r[u]==r[v];
	}
};
#define left afsjlk
dsu x;
set<pair<int, int>> left;
void initialize(int n) {
	x.init(n);
	for(int i = 0; i < n; i++)
	for(int j = i+1; j < n; j++)
	left.insert({i, j});
}

int hasEdge(int u, int v) {
	if(u>v)swap(u, v);
	left.erase({u, v});
	if((u=x.par(u))==(v=x.par(v)))
    return 1;
    int t = 1;
	for(auto i : left) {
		if(minmax(x.par(i.first), x.par(i.second))==minmax(u, v))t++;
		if(t>1) break;
	}
	if(t==1) x.unite(u, v);
	return t==1;
}

/*
int main() {
	cin.tie(0);
	initialize(4);
	for(int f, t, i = 0; i < 6; i++) {
		cin >> f >> t;
		cout << hasEdge(f, t) << "\n";
	}
}
*/

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