oj.uz

Submission #894674

# Submission time Handle Problem Language Result Execution time Memory
894674 2023-12-28T16:46:24 Z OAleksa Dragon 2 (JOI17_dragon2) C++14
60 / 100
 4000 ms 3464 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
const int N = 3e4 + 69;
struct point {
	int x, y;
} a[N], s, e;
vector<point> g[N];
int n, m, q, c[N];
inline int cross(point a, point b, point c) {
	point v = {b.x - a.x, b.y - a.y};
	point v1 = {c.x - a.x, c.y - a.y};
	int r = v1.x * v.y - v1.y * v.x;
	assert(r != 0);
	if (r > 0)
		return 1; //desno
	return -1; //levo
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
		cin >> n >> m;
		for (int i = 1;i <= n;i++) {
			cin >> a[i].x >> a[i].y >> c[i];
			g[c[i]].push_back(a[i]);
		}
		cin >> s.x >> s.y >> e.x >> e.y;
		cin >> q;
		while (q--) {
			int a, b;
			cin >> a >> b;
			int ans = 0;
			for (auto u : g[a]) {
				int d5 = cross(s, e, u);
				for (auto t : g[b]) {
					//ili je u trouglu
					//ili se seku duzi
					int d = cross(u, s, t);
					int d1 = cross(s, e, t);
					int d2 = cross(e, u ,t);
					int d3 = cross(u, t, s);
					int d4 = cross(u, t, e);
					if (d == d1 && d1 == d2)
						++ans;
					else if (d3 != d4 && d5 != d1)
						++ans;
				}
			}
			cout << ans << '\n';
		}
  }
  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1116 KB Output is correct
2 Correct 35 ms 1336 KB Output is correct
3 Correct 42 ms 1116 KB Output is correct
4 Correct 33 ms 1416 KB Output is correct
5 Correct 24 ms 1372 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 12 ms 1328 KB Output is correct
9 Correct 12 ms 1116 KB Output is correct
10 Correct 14 ms 1116 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2013 ms 2472 KB Output is correct
2 Correct 3838 ms 2708 KB Output is correct
3 Correct 75 ms 2648 KB Output is correct
4 Correct 9 ms 2652 KB Output is correct
5 Correct 10 ms 2604 KB Output is correct
6 Correct 1520 ms 2560 KB Output is correct
7 Correct 1482 ms 2756 KB Output is correct
8 Correct 1124 ms 2544 KB Output is correct
9 Correct 1035 ms 2396 KB Output is correct
10 Correct 1100 ms 2592 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1116 KB Output is correct
2 Correct 35 ms 1336 KB Output is correct
3 Correct 42 ms 1116 KB Output is correct
4 Correct 33 ms 1416 KB Output is correct
5 Correct 24 ms 1372 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 12 ms 1328 KB Output is correct
9 Correct 12 ms 1116 KB Output is correct
10 Correct 14 ms 1116 KB Output is correct
11 Correct 2013 ms 2472 KB Output is correct
12 Correct 3838 ms 2708 KB Output is correct
13 Correct 75 ms 2648 KB Output is correct
14 Correct 9 ms 2652 KB Output is correct
15 Correct 10 ms 2604 KB Output is correct
16 Correct 1520 ms 2560 KB Output is correct
17 Correct 1482 ms 2756 KB Output is correct
18 Correct 1124 ms 2544 KB Output is correct
19 Correct 1035 ms 2396 KB Output is correct
20 Correct 1100 ms 2592 KB Output is correct
21 Correct 1990 ms 2552 KB Output is correct
22 Correct 3903 ms 2544 KB Output is correct
23 Correct 3496 ms 2900 KB Output is correct
24 Correct 828 ms 3464 KB Output is correct
25 Correct 46 ms 2804 KB Output is correct
26 Correct 33 ms 2780 KB Output is correct
27 Correct 11 ms 2652 KB Output is correct
28 Correct 11 ms 2648 KB Output is correct
29 Execution timed out 4064 ms 2992 KB Time limit exceeded
30 Halted 0 ms 0 KB -