Submission #709353

#	Time	Username	Problem	Language	Result	Execution time	Memory
709353		600Mihnea	Game (APIO22_game)	C++17	60 / 100	4024 ms	45068 KiB

game

#include <cstdio>
#include <cstdlib>
#include <vector>
#include "game.h"

#include "game.h"
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>

using namespace std;

const int R = 50;

bool F;
int n;
int k;
vector<bool> req;
vector<vector<int>> g;
vector<vector<int>> ig;
vector<int> minAjungBucket;
vector<int> minAjung;

int getbucket(int x)
{
	return x / R;
}

void init(int nn, int kk)
{
	F = 0;
	n = nn;
	k = kk;
	minAjung.clear();
	g.clear();
	ig.clear();
	req.clear();

	g.resize(n + 1);
	ig.resize(n + 1);
	minAjungBucket.resize(n + 1);
	minAjung.resize(n + 1);
	req.resize(n + 1, 0);

	for (int i = 1; i <= n; i++)
	{
		minAjungBucket[i] = (int)1e9 + 7;
		minAjung[i] = k + 1;
	}
}

void upd(int from)
{
	if (F)
	{
		return;
	}
	if (from <= k && minAjung[from] <= from)
	{
		F = 1;
	}
	for (auto& vec : ig[from])
	{
		if (minAjung[from] < minAjung[vec])
		{
			minAjung[vec] = minAjung[from];
			upd(vec);
		}
	}
}

void send_req_all(int from)
{
	if (req[from]) return;
	req[from] = 1;
	for (auto& to : g[from])
	{
		int val = ((to <= k) ? (to) : (minAjung[to]));
		if (val < minAjung[from] && req[from])
		{
			minAjung[from] = val;
			upd(from);
		}
	}
	for (auto& to : g[from])
	{
		send_req_all(to);
	}
}

void updBucket(int from)
{
	if (F)
	{
		return;
	}
	if (from <= k && minAjungBucket[from] == getbucket(from))
	{
		send_req_all(from);
	}
	if (from <= k && minAjungBucket[from] < getbucket(from))
	{
		F = 1;
	}
	for (auto& vec : ig[from])
	{
		if (minAjungBucket[from] < minAjungBucket[vec])
		{
			minAjungBucket[vec] = minAjungBucket[from];
			updBucket(vec);
		}
	}
}

int add_teleporter(int from, int to)
{
	from++;
	to++;

	assert(1 <= from && from <= n);
	assert(1 <= to && to <= n);
	if (req[to] == 0 && req[from] == 1)
	{
		send_req_all(to);
	}
	g[from].push_back(to);
	ig[to].push_back(from);
	{
		int val = ((to <= k) ? (getbucket(to)) : (minAjungBucket[to]));
		if (val < minAjungBucket[from])
		{
			minAjungBucket[from] = val;
			updBucket(from);
		}
	}
	{
		int val = ((to <= k) ? (to) : (minAjung[to]));
		if (val < minAjung[from] && req[from])
		{
			minAjung[from] = val;
			upd(from);
		}
	}


	return F;
}

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