Submission #787388

# Submission time Handle Problem Language Result Execution time Memory
787388 2023-07-19T06:43:08 Z 박영우(#10035) 도로 건설 사업 (JOI13_construction) C++17
0 / 100
1 ms 468 KB
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 22
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
vector<pair<int, pii>> hst, vst;
pii edges[MAX];
int W[MAX];
pii point[MAX];
int p[MAX];
int find(int a) {
	if (p[a] == a) return a;
	return p[a] = find(p[a]);
}
bool uni(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return false;
	p[a] = b;
	return true;
}
int cv[MAX];
ll psum[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, M, C;
	cin >> N >> M >> C;
	int i, a, b, c, d;
	for (i = 1; i <= N; i++) cin >> point[i].first >> point[i].second;
	for (i = 1; i <= M; i++) {
		cin >> a >> b >> c >> d;
		hst.emplace_back(b, pii(a, c));
		hst.emplace_back(d, pii(a, c));
		vst.emplace_back(a, pii(b, d));
		vst.emplace_back(c, pii(b, d));
	}
	sort(hst.begin(), hst.end());
	sort(vst.begin(), vst.end());
	map<int, int> mp;
	vector<int> v;
	for (i = 1; i <= N; i++) v.push_back(i);
	sort(v.begin(), v.end(), [&](int a, int b) {return point[a].first < point[b].first; });
	int cnt = 0, ptr;
	ptr = 0;
	for (auto x : v) {
		while (ptr < M * 2 && point[x].first > vst[ptr].first) {
			auto [l, r] = vst[ptr++].second;
			while (1) {
				auto it = mp.lower_bound(l);
				if (it == mp.end()) break;
				if (it->first > r) break;
				mp.erase(it);
			}
		}
		if (mp.find(point[x].second) != mp.end()) edges[++cnt] = pii(x, mp[point[x].second]);
		mp[point[x].second] = x;
	}
	mp.clear();
	ptr = 0;
	for (auto x : v) {
		while (ptr < M * 2 && point[x].second > hst[ptr].first) {
			auto [l, r] = hst[ptr++].second;
			while (1) {
				auto it = mp.lower_bound(l);
				if (it == mp.end()) break;
				if (it->first > r) break;
				mp.erase(it);
			}
		}
		if (mp.find(point[x].first) != mp.end()) edges[++cnt] = pii(x, mp[point[x].first]);
		mp[point[x].first] = x;
	}
	for (i = 1; i <= cnt; i++) W[i] = abs(point[edges[i].first].first - point[edges[i].second].first) + abs(point[edges[i].first].second - point[edges[i].second].second);
	for (i = 1; i <= N; i++) p[i] = i;
	vector<int> ev;
	for (i = 1; i <= cnt; i++) ev.push_back(i);
	sort(ev.begin(), ev.end(), [&](int a, int b) {return W[a] < W[b]; });
	int ecnt = 0;
	for (auto e : ev) if (uni(edges[e].first, edges[e].second)) cv[++ecnt] = W[e], psum[ecnt] = psum[ecnt - 1] + cv[ecnt];
	int h;
	while (C--) {
		cin >> b >> h;
		if (ecnt + h < N) {
			cout << -1 << ln;
			continue;
		}
		int ind = lower_bound(cv + 1, cv + ecnt + 1, b) - cv;
		ll ans = 1ll * (N - ind + 1) * b;
		ans += psum[ind - 1];
		cout << ans << ln;
	}
}
# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -