Submission #193141

#	Time	Username	Problem	Language	Result	Execution time	Memory
193141		anubhavdhar	Game (IOI14_game)	C++14	100 / 100	503 ms	25316 KiB

game

#include<bits/stdc++.h>

#define ll long long int
#define pb push_back
#define mp make_pair
#define FOR(i,n) for(i=0;i<n;i++)
#define FORe(i,n) for(i=1;i<=n;i++)
#define FORr(i,a,b) for(i=a;i<b;i++)
#define ii pair<ll,ll>
#define vi vector<ll>
#define vii vector<ii>
#define ff first 
#define ss second
#define cd complex<double>
#define vcd vector<cd>

#define MAXN 1505

using namespace std;

#include "game.h"

/*
const ll MAXN = 1511;//2e5+5;
const ll MOD = 1e9+7;
const ll ROOTN = 320;
const ll LOGN = 17;
const ll INF = 1e17 + 1101;
*/
int g[MAXN][MAXN],id[MAXN],sz[MAXN],N;

inline int root(int x)
{
	while(x != id[x])
	{
		id[x] = id[id[x]];
		x = id[x];
	}
	return x;
}
/*
inline void DBG()
{
	ll i;
	FOR(i,N)
		cout<<"id["<<i<<"] = "<<i<<endl;
}
*/
inline void mrg(int a,int b)
{
	int i,x = root(a),y = root(b);
	if(x != y)
	{
		if (sz[x] > sz[y])
			swap(x,y);
		id[x] = y;
		sz[y] += sz[x];
		sz[x] = 0;
		FOR(i,N)
			if(sz[i])
				g[y][i] = g[i][y] = g[i][y] + g[i][x];
	}
}

void initialize(int n)
{
	N = n;
	int i,j;
	FOR(i,N)
	{
		id[i] = i;
		sz[i] = 1;
		FOR(j,N)
			g[i][j] = 0;
	}

	//DBG();

}

int hasEdge(int u,int v)
{
	int p = root(u),q = root(v);
	if (p == q)
	{
		cout<<"DANGER";
		return -1;
	}
	g[p][q]++;
	g[q][p]++;
	if (g[p][q] == sz[p]*sz[q])
	{
		mrg(p,q);
		return 1;
	}
	return 0;
}
/*
inline void PlayGame(ll r)
{
	ll a,b;
	while(r--)
	{
		cin>>a>>b;
		cout<<hasEdge(a,b)<<endl;
	}
}

int main()
{
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	ll n;
	cin>>n;
	initialize(n);
	PlayGame((n*(n-1))/2);
	return 0;
}*/

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