oj.uz

Submission #1099421

# Submission time Handle Problem Language Result Execution time Memory
1099421 2024-10-11T09:34:59 Z TrieTr Park (BOI16_park) C++14
100 / 100
 244 ms 71312 KB 
#include<bits/stdc++.h>
using namespace std;

void local() {
    #define taskname ""
    if (fopen(taskname".inp", "r")) {
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
}

#define ll long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

template<class X, class Y> bool mini(X &a, const Y &b) {return (a > b) ? a = b, true : false;}
template<class X, class Y> bool maxi(X &a, const Y &b) {return (a < b) ? a = b, true : false;}

const int N = 1e6 + 5;

struct DSU {
	vector<int>lab;
	void init(int n) {
		lab.assign(n + 5, -1);
	}
	int find_set(int u) {
		return lab[u] < 0 ? u : lab[u] = find_set(lab[u]);
	}
	int sz(int u) {
		return -lab[find_set(u)];
	}
	bool check(int a, int b) {
		a = find_set(a); b = find_set(b);
		return a == b ? true : false;
	}
	bool unite(int a, int b) {
		a = find_set(a); b = find_set(b);
		if(a == b) return false;
		if(lab[a] > lab[b]) swap(a, b);
		lab[a] += lab[b]; lab[b] = a;
		return true;
	}
} dsu;
struct Circle {
	int x, y, r;
	Circle() {x = y = r = 0;}
	Circle(int x_, int y_, int r_) : x(x_), y(y_), r(r_) {}
} a[N];
int n, m, w, h;
vector<tuple<int, int, int>>edge, event;
vector<pair<int, int>>v[5][5];
string res[N];


ll square(ll x) {
	return x * x;
}
int dist(Circle x, Circle y) {
	//cout << x.x << ' ' << x.y << ' ' << y.x << ' ' << y.y << '\n';
	//cout << sqrt(square(x.x - y.x) + square(x.y - y.y)) << ' ' << x.r << ' ' << y.r << '\n';
	return sqrt(square(x.x - y.x) + square(x.y - y.y)) - x.r - y.r;
}
int main() {
    fastio; local();
    cin >> n >> m >> w >> h;
    for(int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y >> a[i].r;
    for(int i = 1; i <= n; i++) {
    	for(int j = i + 1; j <= n; j++) {
    		edge.emplace_back(dist(a[i], a[j]), i, j);
    	}
    }
    for(int i = 1; i <= n; i++) {
    	edge.emplace_back(dist(a[i], Circle(a[i].x, 0, 0)), i, n + 1);
    	edge.emplace_back(dist(a[i], Circle(0, a[i].y, 0)), i, n + 2);
    	edge.emplace_back(dist(a[i], Circle(a[i].x, h, 0)), i, n + 3);
    	edge.emplace_back(dist(a[i], Circle(w, a[i].y, 0)), i, n + 4);
    }
    for(int i = 1; i <= m; i++) {
    	int r, e; cin >> r >> e;
    	event.emplace_back(r, e, i);
    }
    dsu.init(n + 4);
    for(int i = 1; i < 5; i++) {
    	for(int j = 1; j < 5; j++) {
    		if(i == j) continue;
    		if(i == 1) v[i][j].emplace_back(n + 2, n + 1);
    		if(i == 2) v[i][j].emplace_back(n + 1, n + 4);
    		if(i == 3) v[i][j].emplace_back(n + 4, n + 3);
    		if(i == 4) v[i][j].emplace_back(n + 3, n + 2);
    	}
    	v[i][(i + 1) % 4 + 1].emplace_back(n + 1, n + 3);
    	v[i][(i + 1) % 4 + 1].emplace_back(n + 2, n + 4);
    	if(i & 1) {
    		v[i][(i + 1) % 4 + 1].emplace_back(n + 1, n + 3);
    		v[i][(i + 2) % 4 + 1].emplace_back(n + 2, n + 4);
    	}
    	else {
    		v[i][(i + 1) % 4 + 1].emplace_back(n + 2, n + 4);
    		v[i][(i + 2) % 4 + 1].emplace_back(n + 1, n + 3);
    	}
    }
    sort(edge.begin(), edge.end());
    sort(event.begin(), event.end());
    int pter = 0;
    for(tuple<int, int, int> t : event) {
    	int r, e, id; tie(r, e, id) = t;
    	while(pter < edge.size() && 2 * r > get<0>(edge[pter])) {
    		dsu.unite(get<1>(edge[pter]), get<2>(edge[pter]));
    		pter++;
    	}
    	for(int j = 1; j < 5; j++) {
    		bool ok = true;
			for(pair<int, int>p : v[e][j]) {
				if(dsu.check(p.first, p.second)) ok = false;
			}
			for(pair<int, int>p : v[j][e]) {
				if(dsu.check(p.first, p.second)) ok = false;
			}
			if(ok) res[id] += char(j + '0');
    	}
    }
    for(int i = 1; i <= m; i++) cout << res[i] << '\n';
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:106:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |      while(pter < edge.size() && 2 * r > get<0>(edge[pter])) {
      |            ~~~~~^~~~~~~~~~~~~
park.cpp: In function 'void local()':
park.cpp:7:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:8:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 68284 KB Output is correct
2 Correct 211 ms 68296 KB Output is correct
3 Correct 211 ms 68284 KB Output is correct
4 Correct 197 ms 68288 KB Output is correct
5 Correct 201 ms 68288 KB Output is correct
6 Correct 204 ms 68292 KB Output is correct
7 Correct 201 ms 68288 KB Output is correct
8 Correct 186 ms 68296 KB Output is correct
9 Correct 20 ms 43352 KB Output is correct
10 Correct 19 ms 43352 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 46352 KB Output is correct
2 Correct 56 ms 46296 KB Output is correct
3 Correct 53 ms 46292 KB Output is correct
4 Correct 53 ms 46244 KB Output is correct
5 Correct 53 ms 46364 KB Output is correct
6 Correct 54 ms 46300 KB Output is correct
7 Correct 58 ms 46276 KB Output is correct
8 Correct 55 ms 46092 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 68284 KB Output is correct
2 Correct 211 ms 68296 KB Output is correct
3 Correct 211 ms 68284 KB Output is correct
4 Correct 197 ms 68288 KB Output is correct
5 Correct 201 ms 68288 KB Output is correct
6 Correct 204 ms 68292 KB Output is correct
7 Correct 201 ms 68288 KB Output is correct
8 Correct 186 ms 68296 KB Output is correct
9 Correct 20 ms 43352 KB Output is correct
10 Correct 19 ms 43352 KB Output is correct
11 Correct 57 ms 46352 KB Output is correct
12 Correct 56 ms 46296 KB Output is correct
13 Correct 53 ms 46292 KB Output is correct
14 Correct 53 ms 46244 KB Output is correct
15 Correct 53 ms 46364 KB Output is correct
16 Correct 54 ms 46300 KB Output is correct
17 Correct 58 ms 46276 KB Output is correct
18 Correct 55 ms 46092 KB Output is correct
19 Correct 243 ms 71084 KB Output is correct
20 Correct 227 ms 71048 KB Output is correct
21 Correct 224 ms 71312 KB Output is correct
22 Correct 235 ms 71056 KB Output is correct
23 Correct 244 ms 71044 KB Output is correct
24 Correct 213 ms 71048 KB Output is correct