Submission #133296

#	Time	Username	Problem	Language	Result	Execution time	Memory
133296		sealnot123	Game (IOI14_game)	C++14	42 / 100	1062 ms	12904 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;
multiset<int> g[N], sqg[N];
multiset<int>::iterator it;
int mk[N];
queue<int> bfs;

bool check(int a){
	int b = a*sq;
	int i, j = 1;
	for(i = b; i < min(b+sq, n); i++){
		mk[i] = 0;
	}
	mk[b] = 1;
	bfs.push(b);
	while(!bfs.empty()){
		int u = bfs.front();
		bfs.pop();
		for(it = g[u].begin(); it!=g[u].end(); it++){
			if(mk[*it]) continue;
			j++;
			mk[*it] = 1;
			bfs.push(*it);
		}
	}
	return j == min(n,b+sq)-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(it = sqg[u].begin(); it != sqg[u].end(); it++){
			if(mk[*it]) continue;
			mk[*it] = 1;
			j++;
			bfs.push(*it);
		}
	}
	return j == a;
}

void initialize(int nn) {
	n = nn;
    LL i, j, a, b, c;
    LL ans = 1e18;
    for(i = 2; i <= n; i++){
        c = (n+i-1)/i;
        a = c*(c-1)*n*n/2 + i*(i-1)*n*i/2;
        if(a < ans) ans = a, sq = i;
    }
	for(i = 0; i < n; i++){
		for(j = i+1; j < n; j++){
			a = i/sq;
			b = j/sq;
			if(a == b) g[i].insert(j), g[j].insert(i);
			else sqg[a].insert(b), sqg[b].insert(a);
		}
	}
}

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].erase(v);
		g[v].erase(u);
		res = check(a);
		if(!res){
			g[u].insert(v);
			g[v].insert(u);
			return 1;
		}
		return 0;
	}else{
		sqg[a].erase(sqg[a].find(b));
		sqg[b].erase(sqg[b].find(a));
		res = check_group();
		if(!res){
			sqg[a].insert(b);
			sqg[b].insert(a);
			return 1;
		}
		return 0;
	}
    return 0;
}

Compilation message (stderr)

game.cpp: In function 'int hasEdge(int, int)':
game.cpp:86:6: warning: unused variable 'i' [-Wunused-variable]
  int i, j, a, b, res;
      ^
game.cpp:86: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