Submission #289144

#	Time	Username	Problem	Language	Result	Execution time	Memory
289144		staniewzki	Dragon 2 (JOI17_dragon2)	C++17	60 / 100	4067 ms	9592 KiB

dragon2

#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 / 15
• Subtask 2: 45 / 45
• Subtask 3: 0 / 40