Submission #127325

#	Time	Username	Problem	Language	Result	Execution time	Memory
127325		nxteru	Game (IOI14_game)	C++14	100 / 100	623 ms	34260 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
struct UF{
	int n,par[1505],rs[1505];
	void ini(int x,int v){
		n=x;
		for(int i=0;i<n;i++){
			par[i]=i;
			if(i==v)rs[i]=0;
			else rs[i]=1;
		}
	}
	int find(int x){
		if(par[x]==x)return x;
		return par[x]=find(par[x]);
	}
	void unit(int v,int u){
		v=find(v);
		u=find(u);
		rs[v]+=rs[u];
		par[u]=v;
	}
};
int n,par[1505];
UF p[1505];
bool rt[1505];
vector<int>rts;
int find(int x){
	if(par[x]==x)return x;
	return par[x]=find(par[x]);
}
void unit(int v,int u){
	v=find(v);
	u=find(u);
	for(int i=0;i<rts.size();i++)p[v].rs[rts[i]]+=p[u].rs[rts[i]];
	par[u]=v;
	rt[u]=false;
}
void initialize(int N) {
	n=N;
	for(int i=0;i<n;i++)par[i]=i,p[i].ini(n,i),rt[i]=true;
}

int hasEdge(int u, int v) {
    u=find(u);
    v=find(v);
    if(u==v)return 1;
    p[u].rs[v]--;
	p[v].rs[u]--;
    if(p[u].rs[v]>0)return 0;
	else{
		rts.clear();
		for(int i=0;i<n;i++)if(rt[i])rts.PB(i);
		for(int i=0;i<rts.size();i++)p[rts[i]].unit(v,u);
		unit(v,u);
		return 1;
	}
}

Compilation message (stderr)

game.cpp: In function 'void unit(int, int)':
game.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<rts.size();i++)p[v].rs[rts[i]]+=p[u].rs[rts[i]];
              ~^~~~~~~~~~~
game.cpp: In function 'int hasEdge(int, int)':
game.cpp:56:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<rts.size();i++)p[rts[i]].unit(v,u);
               ~^~~~~~~~~~~

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