oj.uz

Submission #283689

# Submission time Handle Problem Language Result Execution time Memory
283689 2020-08-26T05:34:51 Z 임성재(#5753) 도로 건설 사업 (JOI13_construction) C++17
40 / 100
 5000 ms 26744 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 1e18;
const ll inf = 1e9;

int n, m, c;
vector<int> v;
vector<pii> e;
int x[200010];
int y[200010];
int p[200010];
int q[200010];
int r[200010];
int s[200010];
int par[200010];
ll sum[200010];
vector<ll> ans;

int Find(int a) { return par[a] = par[a] == a ? a : Find(par[a]); }
void Union(int a, int b) { par[Find(b)] = Find(a); }

bool chk(int i, int j) {
	if(mp(x[i], y[i]) > mp(x[j], y[j])) swap(i, j);

	for(int k=1; k<=m; k++) {
		if(max(x[i], p[k]) <= min(x[j], r[k]) && max(y[i], q[k]) <= min(y[j], s[k])) return false;
	}

	return true;
}

int main() {
	fast;

	cin >> n >> m >> c;

	for(int i=1; i<=n; i++) {
		cin >> x[i] >> y[i];
		v.eb(i);
		par[i] = i;
	}

	for(int i=1; i<=m; i++) {
		cin >> p[i] >> q[i] >> r[i] >> s[i];
	}

	sort(all(v), [&](int i, int j) { return mp(x[i], y[i]) < mp(x[j], y[j]); });

	for(int i=1; i<v.size(); i++) {
		if(x[v[i]] == x[v[i-1]] && chk(v[i-1], v[i])) {
			e.eb(v[i-1], v[i]);
		}
	}

	sort(all(v), [&](int i, int j) { return mp(y[i], x[i]) < mp(y[j], x[j]); });

	for(int i=1; i<v.size(); i++) {
		if(y[v[i]] == y[v[i-1]] && chk(v[i-1], v[i])) {
			e.eb(v[i-1], v[i]);
		}
	}

	sort(all(e), [&](pii i, pii j) {
		return abs(x[i.fi] - x[i.se] + y[i.fi] - y[i.se]) < abs(x[j.fi] - x[j.se] + y[j.fi] - y[j.se]);
	});

	for(auto i : e) {
		if(Find(i.fi) == Find(i.se)) continue;

		Union(i.fi, i.se);
		ans.eb(abs(x[i.fi] - x[i.se] + y[i.fi] - y[i.se]));
	}

	sort(all(ans));

	for(int i=0; i<ans.size(); i++) {
		sum[i+1] = sum[i] + ans[i];
	}

	while(c--) {
		ll b, h;
		cin >> b >> h;

		ll k = upper_bound(all(ans), b) - ans.begin();

		k = max(k, n - h);

		if(k <= ans.size()) {
			cout << sum[k] + (n - k) * b << "\n";
		}
		else cout << "-1\n";
	}
}

Compilation message

construction.cpp: In function 'int main()':
construction.cpp:61:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i=1; i<v.size(); i++) {
      |               ~^~~~~~~~~
construction.cpp:69:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(int i=1; i<v.size(); i++) {
      |               ~^~~~~~~~~
construction.cpp:88:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  for(int i=0; i<ans.size(); i++) {
      |               ~^~~~~~~~~~~
construction.cpp:100:8: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |   if(k <= ans.size()) {
      |      ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 640 KB Output is correct
2 Correct 183 ms 9708 KB Output is correct
3 Correct 202 ms 9836 KB Output is correct
4 Correct 274 ms 13676 KB Output is correct
5 Correct 192 ms 12268 KB Output is correct
6 Correct 191 ms 9968 KB Output is correct
7 Correct 188 ms 15080 KB Output is correct
8 Correct 176 ms 12264 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 640 KB Output is correct
2 Correct 183 ms 9708 KB Output is correct
3 Correct 202 ms 9836 KB Output is correct
4 Correct 274 ms 13676 KB Output is correct
5 Correct 192 ms 12268 KB Output is correct
6 Correct 191 ms 9968 KB Output is correct
7 Correct 188 ms 15080 KB Output is correct
8 Correct 176 ms 12264 KB Output is correct
9 Correct 1329 ms 18424 KB Output is correct
10 Correct 1301 ms 18492 KB Output is correct
11 Correct 912 ms 18512 KB Output is correct
12 Correct 973 ms 18416 KB Output is correct
13 Execution timed out 5089 ms 12400 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 640 KB Output is correct
2 Correct 183 ms 9708 KB Output is correct
3 Correct 202 ms 9836 KB Output is correct
4 Correct 274 ms 13676 KB Output is correct
5 Correct 192 ms 12268 KB Output is correct
6 Correct 191 ms 9968 KB Output is correct
7 Correct 188 ms 15080 KB Output is correct
8 Correct 176 ms 12264 KB Output is correct
9 Correct 444 ms 25884 KB Output is correct
10 Correct 479 ms 24292 KB Output is correct
11 Correct 421 ms 21744 KB Output is correct
12 Correct 438 ms 23148 KB Output is correct
13 Correct 337 ms 19800 KB Output is correct
14 Correct 430 ms 26320 KB Output is correct
15 Correct 444 ms 25152 KB Output is correct
16 Correct 437 ms 23920 KB Output is correct
17 Correct 383 ms 26744 KB Output is correct
18 Correct 420 ms 23216 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 640 KB Output is correct
2 Correct 183 ms 9708 KB Output is correct
3 Correct 202 ms 9836 KB Output is correct
4 Correct 274 ms 13676 KB Output is correct
5 Correct 192 ms 12268 KB Output is correct
6 Correct 191 ms 9968 KB Output is correct
7 Correct 188 ms 15080 KB Output is correct
8 Correct 176 ms 12264 KB Output is correct
9 Correct 1329 ms 18424 KB Output is correct
10 Correct 1301 ms 18492 KB Output is correct
11 Correct 912 ms 18512 KB Output is correct
12 Correct 973 ms 18416 KB Output is correct
13 Execution timed out 5089 ms 12400 KB Time limit exceeded
14 Halted 0 ms 0 KB -