Submission #133280

#	Time	Username	Problem	Language	Result	Execution time	Memory
133280		sealnot123	Game (IOI14_game)	C++14	42 / 100	1070 ms	8560 KiB

game

#include "game.h"

#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef double D;
typedef long double LD;
const int N = 1505, SQ = 39;
int n, sq;
int sqg[N][N], g[N][N], l[N], r[N];
int mk[N];
queue<int> bfs;

bool check(int a){
	int b = a*sq;
	int i, j = 1;
	for(i = l[b]; i < r[b]; i++){
		mk[i] = 0;
	}
	mk[b] = 1;
	bfs.push(b);
	while(!bfs.empty()){
		int u = bfs.front();
		bfs.pop();
		for(i = l[u]; i < r[u]; i++){
			if(!g[u][i] || mk[i]) continue;
			j++;
			mk[i] = 1;
			bfs.push(i);
		}
	}
	return j == r[b]-l[b];
}

bool check_group(){
	int a = (n+sq-1)/sq;
	int i, j = 1;
	for(i = 0; i < a; i++){
		mk[i] = 0;
	}
	mk[0] = 1;
	bfs.push(0);
	while(!bfs.empty()){
		int u = bfs.front();
		bfs.pop();
		for(i = 0; i < a; i++){
			if(!sqg[u][i] || mk[i]) continue;
			mk[i] = 1;
			j++;
			bfs.push(i);
		}
	}
	return j == a;
}

void initialize(int nn) {
	n = nn;
	sq = sqrt(nn);
	int i, j, a, b;
	for(i = 0; i < n; i++){
		for(j = i+1; j < n; j++){
			a = i/sq;
			b = j/sq;
			if(a == b) g[i][j] = g[j][i] = 1;
			else sqg[a][b]++,sqg[b][a]++;
		}
		l[i] = i/sq*sq;
		r[i] = min(i/sq*sq+sq, n);
	}
}

int hasEdge(int u, int v) {
	if(u > v) swap(u, v);
	int i, j, a, b, res;
	a = u/sq;
	b = v/sq;
	if(a == b){
		g[u][v] = g[v][u] = 0;
		res = check(a);
		if(!res){
			g[u][v] = g[v][u] = 1;
			return 1;
		}
		return 0;
	}else{
		sqg[a][b]--;
		sqg[b][a]--;
		res = check_group();
		if(!res){
			sqg[a][b]++;
			sqg[b][a]++;
			return 1;
		}
		return 0;
	}
    return 0;
}

Compilation message (stderr)

game.cpp: In function 'int hasEdge(int, int)':
game.cpp:82:6: warning: unused variable 'i' [-Wunused-variable]
  int i, j, a, b, res;
      ^
game.cpp:82:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, a, b, res;
         ^

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