Submission #596145

#	Time	Username	Problem	Language	Result	Execution time	Memory
596145		mohammad_kilani	Game (APIO22_game)	C++17	100 / 100	1398 ms	54740 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

int n , k;

vector< int > mx , mn , l , r;

vector< vector< int > > g , g2;

bool fixNode(int node){
	if(mx[node] >= mn[node])
		return false;
	int mid;
	bool good = false;
	while(l[node] < r[node]){
		mid = (l[node] + r[node]) / 2;
		if(mn[node] <= mid){
			r[node] = mid;
			good = true;
		}
		else if(mx[node] > mid){
			l[node] = mid + 1;
			good = true;
		}
		else
			break;
	}
	return good;
}

void init(int n, int k) {
	::n = n;
	::k = k;
	mx.resize(n , 0);
	mn.resize(n , k + 1);
	l.resize(n , 0);
	r.resize(n , k + 1);

	for(int i = 0 ;i < k;i++){
		mn[i] = mx[i] = i + 1;
	}
	g.resize(n);
	g2.resize(n);
}

void DFSMax(int node){
	for(int i = 0 ;i < (int)g[node].size();i++){
		if(g[node][i] < k){
			mn[node] = min(mn[node] , g[node][i] + 1);
			continue;
		}
		mx[g[node][i]] = max(mx[g[node][i]] , mx[node]);
		if(fixNode(g[node][i])){
			DFSMax(g[node][i]);
		}
		mn[node] = min(mn[node] , mn[g[node][i]]);
	}
	fixNode(node);
}

void DFSMin(int node){
	for(int i = 0 ;i < (int)g2[node].size();i++){
		if(g2[node][i] < k){
			mx[node] = max(mx[node] , g2[node][i] + 1);
			continue;
		}
		mn[g2[node][i]] = min(mn[g2[node][i]] , mn[node]);
		if(fixNode(g2[node][i])){
			DFSMin(g2[node][i]);
		}
		mx[node] = max(mx[node] , mx[g2[node][i]]);
	}
	fixNode(node);
}

int add_teleporter(int u, int v) {
	if(u < k && v < k){
		if(u >= v)
			return 1;
		return 0;
	}
	g[u].push_back(v);
	g2[v].push_back(u);


	//fix max
	if(v >= k){
		mx[v] = max(mx[v] , mx[u]);
		if(fixNode(v)){
			DFSMax(v);
			DFSMin(v);
		}

		if(mx[v] >= mn[v])
			return 1;
	}
	//fix min
	if(u >= k){
		mn[u] = min(mn[u] , mn[v]);
		if(fixNode(u)){
			DFSMin(u);
			DFSMax(u);
		}
		if(mx[u] >= mn[u])
			return 1;
	}
 	return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 30 / 30
• Subtask 5: 40 / 40