oj.uz

Submission #106711

# Submission time Handle Problem Language Result Execution time Memory
106711 2019-04-19T18:52:01 Z chemistrae03 Circle selection (APIO18_circle_selection) C++17
0 / 100
 4 ms 1280 KB 
#include <bits/stdc++.h>

using namespace std;

struct Circle {
	int x, y, r, i;
	Circle(int _x, int _y, int _r, int _i) : x(_x), y(_y), r(_r), i(_i) {
		// do nothing
	}
	bool intercept(const Circle &c) {
		int dx = c.x - x, dy = c.y - y, dr = c.r + r;
		// cerr << dx << ' ' << dy << ' ' << dr << '\n';
		if (dx * dx + dy * dy <= dr * dr) {
			return true;
		} else {
			return false;
		}
	}
	bool operator < (const Circle &c) { 
		return r == c.r ? i < c.i : r > c.r;
	}
};

const int MAX = 1e5 + 9;
vector<Circle> v;
int parent[MAX];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	// Circle c1 = Circle(9, 8, 5, 1);
	// Circle c2 = Circle(2, 8, 2, 1);
	// cerr << c1.intercept(c2) << '\n';
	// return 0;
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}
	for (int i = 0; i < n; i++) {
		int x, y, r;
		cin >> x >> y >> r;
		v.emplace_back(x, y, r, i + 1);
	}
	sort(v.begin(), v.end());
	// for (auto vv : v) {
	// 	cerr << vv.i << '\n';
	// }
	// return 0;
	for (auto vv : v) {
		if (parent[vv.i] == vv.i) {
			for (auto vvv : v) {
				if (parent[vvv.i] != vvv.i) {
					continue;
				}
				if (vv.intercept(vvv)) {
					parent[vvv.i] = vv.i;
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << parent[i] << ' ';
	}
	cout << '\n';
	return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -