oj.uz

Submission #236757

# Submission time Handle Problem Language Result Execution time Memory
236757 2020-06-03T08:35:12 Z BamiTorabi Park (BOI16_park) C++14
100 / 100
 700 ms 33528 KB 
//Sasayego! Sasayego! Shinzou wo Sasageyo!

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bitset>
#include <ctime>
#define debug(x)  cerr << #x << " = " << x << endl
#define lid (id << 1)
#define rid (lid ^ 1)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
typedef pair <ll, pii> edge;

const int maxN = 2e3 + 5;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

int arumin[4][4], m, par[maxN];
int X[maxN], Y[maxN], rad[maxN];
edge E[maxN * maxN];

ll SQ(ll x){
	ll lt = 0, rt = MOD;
	while (rt - lt > 1){
		ll md = (lt + rt) >> 1;
		(md * md > x ? rt : lt) = md;
	}
	return rt;
}

ll dist(int a, int b){
	ll x = X[a] - X[b];
	ll y = Y[a] - Y[b];
	return SQ(x * x + y * y);
}

int getpar(int v){
	return (par[v] == v ? v : par[v] = getpar(par[v]));
}

void join(int u, int v){
	u = getpar(u);
	v = getpar(v);
	par[u] = v;
	return;
}

void put(int a, int b, int x){
	arumin[a][b] = min(arumin[a][b], x);
	arumin[b][a] = min(arumin[b][a], x);
	return;
}

int main(){
	time_t START = clock();
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	iota(par, par + maxN, 0);
	int n, q; scanf("%d%d", &n, &q);
	int w, h; scanf("%d%d", &w, &h);
	E[m++] = {w, {0, 2}};
	E[m++] = {h, {1, 3}};
	for (int i = 4; i < n + 4; i++){
		scanf("%d%d%d", X + i, Y + i, rad + i);
		E[m++] = {X[i] - rad[i], {0, i}};
		E[m++] = {Y[i] - rad[i], {1, i}};
		E[m++] = {w - X[i] - rad[i], {2, i}};
		E[m++] = {h - Y[i] - rad[i], {3, i}};
		for (int j = 4; j < i; j++)
			E[m++] = {dist(j, i) - rad[i] - rad[j], {j, i}};
	}
	sort(E, E + m);
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			arumin[i][j] = MOD;
	for (int x = 0; x < m; x++){
		int d, a, b; pii pp;
		tie(d, pp) = E[x];
		tie(a, b) = pp;
		join(a, b);
		for (int i = 0; i < 4; i++)
			for (int j = i + 1; j < 4; j++)
				if (getpar(i) == getpar(j)){
					if ((4 + i - j) & 1){
						for (int k = 0; k < 4; k++)
							if ((i == 0 && j == 3 ? j : i) != k)
								put((i == 0 && j == 3 ? j : i), k, d);
					}
					else{
						for (int k = 0; k < 2; k++)
							for (int l = 0; l < 2; l++)
								put((i + k) & 3, (j + l) & 3, d);
					}
				}
	}
	while (q--){
		int r, p; scanf("%d%d", &r, &p);
		p--; r <<= 1;
		for (int i = 0; i < 4; i++)
			if (r < arumin[p][i])
				printf("%d", i + 1);
		printf("\n");
	}
	time_t FINISH = clock();
	cerr << "Execution time: " << (ld)(FINISH - START) / CLOCKS_PER_SEC * 1000.0 << " milliseconds.\n";
	return 0;
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:72:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, q; scanf("%d%d", &n, &q);
            ~~~~~^~~~~~~~~~~~~~~~
park.cpp:73:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int w, h; scanf("%d%d", &w, &h);
            ~~~~~^~~~~~~~~~~~~~~~
park.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", X + i, Y + i, rad + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:110:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int r, p; scanf("%d%d", &r, &p);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 648 ms 31864 KB Output is correct
2 Correct 643 ms 31992 KB Output is correct
3 Correct 653 ms 31992 KB Output is correct
4 Correct 647 ms 31992 KB Output is correct
5 Correct 644 ms 31868 KB Output is correct
6 Correct 641 ms 31956 KB Output is correct
7 Correct 536 ms 32120 KB Output is correct
8 Correct 539 ms 31992 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 1144 KB Output is correct
2 Correct 65 ms 1016 KB Output is correct
3 Correct 65 ms 2040 KB Output is correct
4 Correct 65 ms 2172 KB Output is correct
5 Correct 65 ms 2168 KB Output is correct
6 Correct 68 ms 2168 KB Output is correct
7 Correct 56 ms 1912 KB Output is correct
8 Correct 56 ms 1912 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 648 ms 31864 KB Output is correct
2 Correct 643 ms 31992 KB Output is correct
3 Correct 653 ms 31992 KB Output is correct
4 Correct 647 ms 31992 KB Output is correct
5 Correct 644 ms 31868 KB Output is correct
6 Correct 641 ms 31956 KB Output is correct
7 Correct 536 ms 32120 KB Output is correct
8 Correct 539 ms 31992 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 68 ms 1144 KB Output is correct
12 Correct 65 ms 1016 KB Output is correct
13 Correct 65 ms 2040 KB Output is correct
14 Correct 65 ms 2172 KB Output is correct
15 Correct 65 ms 2168 KB Output is correct
16 Correct 68 ms 2168 KB Output is correct
17 Correct 56 ms 1912 KB Output is correct
18 Correct 56 ms 1912 KB Output is correct
19 Correct 696 ms 33272 KB Output is correct
20 Correct 692 ms 33528 KB Output is correct
21 Correct 696 ms 33400 KB Output is correct
22 Correct 693 ms 33112 KB Output is correct
23 Correct 700 ms 33272 KB Output is correct
24 Correct 588 ms 33272 KB Output is correct