oj.uz

Submission #289144

# Submission time Handle Problem Language Result Execution time Memory
289144 2020-09-02T12:09:25 Z staniewzki Dragon 2 (JOI17_dragon2) C++17
60 / 100
 4000 ms 9592 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
 
ostream& operator<<(ostream &out, string str) {
	for(char c : str) out << c;
	return out;
}
 
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
	return out << "(" << p.ST << ", " << p.ND << ")";
}

template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) {
	out << '{';
	for(auto &e : x)
        	out << e << (&e == &*--x.end() ? "" : ", ");
	return out << '}';
}

#ifdef DEBUG
template<class... Args> void dump(Args&&... args) {
	((cerr << args << ";  "), ...);
}
#  define debug(x...) cerr << "[" #x "]: ", dump(x), cerr << "\n"
#else
#  define debug(...) false
#endif
 
template<class T> int size(T && a) { return (int) a.size(); }
 
using LL = long long;
using PII = pair<int, int>;

LL operator*(PII a, PII b) {
	return (LL) a.ST * b.ND - (LL) a.ND * b.ST;
}

bool clockwise(PII a, PII b, PII c) { 
	return a * b + b * c + c * a <= 0;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, m;
	cin >> n >> m;

	vector<vector<PII>> pts(m);
	REP(i, n) {
		int a, b, c;
		cin >> a >> b >> c;
		pts[c - 1].emplace_back(a, b);
	}

	PII s, t;
	cin >> s.ST >> s.ND >> t.ST >> t.ND;

	int q;
	cin >> q;

	map<PII, int> mem;
	REP(i, q) {
		int f, g;
		cin >> f >> g;
		f--, g--;

		PII state(f, g);
		if(mem.count(state)) {
			cout << mem[state] << "\n";
			continue;
		}
		int &ans = mem[state];

		for(PII x : pts[f]) {
			for(PII y : pts[g]) {
				if(clockwise(s, t, x))
					ans += clockwise(x, s, y) && clockwise(y, t, x);
				else
					ans += clockwise(x, t, y) && clockwise(y, s, x);
			}
		}
		cout << ans << "\n";
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 512 KB Output is correct
2 Correct 25 ms 384 KB Output is correct
3 Correct 35 ms 768 KB Output is correct
4 Correct 122 ms 7672 KB Output is correct
5 Correct 129 ms 7928 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 10 ms 512 KB Output is correct
9 Correct 8 ms 384 KB Output is correct
10 Correct 13 ms 384 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1695 ms 1460 KB Output is correct
2 Correct 2843 ms 1416 KB Output is correct
3 Correct 66 ms 1536 KB Output is correct
4 Correct 14 ms 1536 KB Output is correct
5 Correct 15 ms 2432 KB Output is correct
6 Correct 1385 ms 1392 KB Output is correct
7 Correct 1722 ms 1392 KB Output is correct
8 Correct 817 ms 1408 KB Output is correct
9 Correct 814 ms 1252 KB Output is correct
10 Correct 802 ms 1264 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 512 KB Output is correct
2 Correct 25 ms 384 KB Output is correct
3 Correct 35 ms 768 KB Output is correct
4 Correct 122 ms 7672 KB Output is correct
5 Correct 129 ms 7928 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 10 ms 512 KB Output is correct
9 Correct 8 ms 384 KB Output is correct
10 Correct 13 ms 384 KB Output is correct
11 Correct 1695 ms 1460 KB Output is correct
12 Correct 2843 ms 1416 KB Output is correct
13 Correct 66 ms 1536 KB Output is correct
14 Correct 14 ms 1536 KB Output is correct
15 Correct 15 ms 2432 KB Output is correct
16 Correct 1385 ms 1392 KB Output is correct
17 Correct 1722 ms 1392 KB Output is correct
18 Correct 817 ms 1408 KB Output is correct
19 Correct 814 ms 1252 KB Output is correct
20 Correct 802 ms 1264 KB Output is correct
21 Correct 1515 ms 1400 KB Output is correct
22 Correct 2817 ms 1432 KB Output is correct
23 Correct 2727 ms 1916 KB Output is correct
24 Correct 812 ms 8816 KB Output is correct
25 Correct 134 ms 8952 KB Output is correct
26 Correct 128 ms 9592 KB Output is correct
27 Correct 22 ms 3968 KB Output is correct
28 Correct 39 ms 3960 KB Output is correct
29 Execution timed out 4067 ms 9244 KB Time limit exceeded
30 Halted 0 ms 0 KB -