oj.uz

Submission #283687

# Submission time Handle Problem Language Result Execution time Memory
283687 2020-08-26T05:31:01 Z 임성재(#5753) 도로 건설 사업 (JOI13_construction) C++17
0 / 100
 20 ms 5632 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;
vector<pii> qr[200010];
vector<int> com;

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--) {
		int b, h;
		cin >> b >> h;

		int 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:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i=1; i<v.size(); i++) {
      |               ~^~~~~~~~~
construction.cpp:75:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for(int i=1; i<v.size(); i++) {
      |               ~^~~~~~~~~
construction.cpp:94:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |  for(int i=0; i<ans.size(); i++) {
      |               ~^~~~~~~~~~~
construction.cpp:106:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |   if(k <= ans.size()) {
      |      ~~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 5632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 5632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 5632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 5632 KB Output isn't correct
2 Halted 0 ms 0 KB -