oj.uz

Submission #708947

# Submission time Handle Problem Language Result Execution time Memory
708947 2023-03-12T19:30:58 Z 600Mihnea Game (APIO22_game) C++17
0 / 100
 0 ms 208 KB 
#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<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();

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

	for (int i = 1; i <= n; i++)
	{
		minAjungBucket[i] = getbucket(k + 1);
		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 updBucket(int from)
{
	if (F)
	{
		return;
	}
	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);

	g[from].push_back(to);
	ig[to].push_back(from);

	{
		int val = ((to <= k) ? (to) : (minAjung[to]));
		if (val < minAjung[from])
		{
			minAjung[from] = val;
			upd(from);
		}
	}
	{
		int val = ((to <= k) ? (getbucket(to)) : (minAjungBucket[to]));
		if (val < minAjungBucket[from])
		{
			minAjungBucket[from] = val;
			updBucket(from);
		}
	}
	return F;
}

Subtask #1
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 0 ms 208 KB Wrong Answer[1]
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 0 ms 208 KB Wrong Answer[1]
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 0 ms 208 KB Wrong Answer[1]
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 0 ms 208 KB Wrong Answer[1]
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 0 ms 208 KB Wrong Answer[1]
4 Halted 0 ms 0 KB -