oj.uz

Submission #105572

# Submission time Handle Problem Language Result Execution time Memory
105572 2019-04-13T13:59:28 Z jwvg0425 도로 건설 사업 (JOI13_construction) C++17
100 / 100
 2655 ms 167324 KB 
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;


class Mapping
{
public:
	void init(const vector<i64>& raw, int base = 0)
	{
		start = base;
		arr = raw;
		sort(arr.begin(), arr.end());
		arr.erase(unique(arr.begin(), arr.end()), arr.end());
	}

	int get_idx(i64 k)
	{
		return start + (lower_bound(all(arr), k) - arr.begin());
	}

	i64 get_value(int idx)
	{
		return arr[idx - start];
	}

	int size()
	{
		return arr.size();
	}

private:
	int start;
	vector<i64> arr;
};

class FenwickTree
{
public:
	FenwickTree(int k)
	{
		data.resize(k);
	}

	i64 sum(int n)
	{
		i64 ans = 0;

		while (n > 0)
		{
			ans += data[n];
			n -= (n & -n);
		}

		return ans;
	}

	void add(int n, i64 num)
	{
		while (n < data.size())
		{
			data[n] += num;
			n += (n & -n);
		}
	}

private:
	vector<i64> data;
};

struct Edge
{
	Edge() = default;

	Edge(int start, int end, int cost)
		: s(start), e(end), c(cost) {}

	int s, e, c;
};

vector<Edge> edges;
int parent[200005];

int find(int x)
{
	if (parent[x] == x)
		return x;

	return parent[x] = find(parent[x]);
}

void merge(int x, int y)
{
	x = find(x);
	y = find(y);

	parent[x] = y;
}

struct Events
{
	//l ~ r 영역(l에 +1, r에 -1)
	vector<ii> area;

	// xpos, idx
	vector<ii> pos;
};

void buildGraph(Mapping& mapping, vector<Events>& events)
{
	FenwickTree cover(mapping.size() + 3);
	FenwickTree points(mapping.size() + 3);

	for (auto& es : events)
	{
		sort(all(es.pos));

		for (auto& area : es.area)
		{
			cover.add(area.xx, 1);
			cover.add(area.yy, -1);

			if (area.xx < area.yy)
				points.add(area.xx, 1);
			else
				points.add(area.yy, -1);
		}

		if (es.pos.empty())
			continue;

		for (int i = 0; i < es.pos.size() - 1; i++)
		{
			int sx = mapping.get_idx(es.pos[i].xx);
			int ex = mapping.get_idx(es.pos[i + 1].xx);

			if (cover.sum(sx) > 0 || cover.sum(ex) > 0)
				continue;

			if (points.sum(ex) - points.sum(sx - 1) > 0)
				continue;

			edges.emplace_back(es.pos[i].yy, es.pos[i + 1].yy,
				es.pos[i + 1].xx - es.pos[i].xx);
		}
	}
}

int main()
{
	int n, m, c;
	scanf("%d %d %d", &n, &m, &c);

	vector<ii> towns(n + 1);
	vector<ii> st(m), ed(m);
	vector<i64> xpos, ypos;

	for (int i = 1; i <= n; i++)
	{
		scanf("%d %d", &towns[i].xx, &towns[i].yy);
		xpos.push_back(towns[i].xx);
		ypos.push_back(towns[i].yy);
	}

	for (int i = 0; i < m; i++)
	{
		scanf("%d %d %d %d", &st[i].xx, &st[i].yy, &ed[i].xx, &ed[i].yy);
		xpos.push_back(st[i].xx);
		xpos.push_back(ed[i].xx);
		xpos.push_back(ed[i].xx + 1);
		ypos.push_back(st[i].yy);
		ypos.push_back(ed[i].yy);
		ypos.push_back(ed[i].yy + 1);
	}

	Mapping xMapping;
	Mapping yMapping;

	xMapping.init(xpos, 1);
	yMapping.init(ypos, 1);


	// y 좌표, (해당 y에서 event)
	vector<Events> xEvents(yMapping.size() + 3);
	vector<Events> yEvents(xMapping.size() + 3);

	for (int i = 1; i <= n; i++)
	{
		xEvents[yMapping.get_idx(towns[i].yy)].pos.emplace_back(towns[i].xx, i);
		yEvents[xMapping.get_idx(towns[i].xx)].pos.emplace_back(towns[i].yy, i);
	}

	for (int i = 0; i < m; i++)
	{
		st[i].yy = yMapping.get_idx(st[i].yy);
		ed[i].yy = yMapping.get_idx(ed[i].yy);
		st[i].xx = xMapping.get_idx(st[i].xx);
		ed[i].xx = xMapping.get_idx(ed[i].xx);
		xEvents[st[i].yy].area.emplace_back(st[i].xx, ed[i].xx + 1);
		xEvents[ed[i].yy + 1].area.emplace_back(ed[i].xx + 1, st[i].xx);

		yEvents[st[i].xx].area.emplace_back(st[i].yy, ed[i].yy + 1);
		yEvents[ed[i].xx + 1].area.emplace_back(ed[i].yy + 1, st[i].yy);
	}

	buildGraph(xMapping, xEvents);
	buildGraph(yMapping, yEvents);

	sort(all(edges), [](const Edge& l, const Edge& r)
	{
		return l.c < r.c;
	});

	vector<int> used;

	for (int i = 1; i <= n; i++)
		parent[i] = i;

	for (auto& e : edges)
	{
		if (find(e.s) == find(e.e))
			continue;

		merge(e.s, e.e);
		used.push_back(e.c);
	}

	int minNeed = 0;

	for (int i = 1; i <= n; i++)
	{
		if (find(i) != i)
			continue;

		minNeed++;
	}

	used.push_back(0); // sentry
	sort(all(used));

	vector<i64> usedSum(used.size());

	for (int i = 1; i < used.size(); i++)
		usedSum[i] = usedSum[i - 1] + used[i];

	for (int i = 0; i < c; i++)
	{
		i64 b, h;
		scanf("%lld %lld", &b, &h);

		if (h < minNeed)
		{
			printf("-1\n");
			continue;
		}

		// 이분 탐색으로, 코스트가 b이상인 맨 왼쪽 간선 찾는다.
		// b이상인것 전부 제외하면 됨
		int ignore = lower_bound(all(used), b) - used.begin();
		int setup = used.size() - ignore;
		int setupMax = h - minNeed;

		setup = min(setup, setupMax);
		ignore = used.size() - setup;

		i64 total = usedSum[ignore - 1]
			+ (minNeed + setup) * b;

		printf("%lld\n", total);
	}

	return 0;
}

Compilation message

construction.cpp: In member function 'void FenwickTree::add(int, i64)':
construction.cpp:82:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (n < data.size())
          ~~^~~~~~~~~~~~~
construction.cpp: In function 'void buildGraph(Mapping&, std::vector<Events>&)':
construction.cpp:154:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < es.pos.size() - 1; i++)
                   ~~^~~~~~~~~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:265:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < used.size(); i++)
                  ~~^~~~~~~~~~~~~
construction.cpp:174:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &c);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:182:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &towns[i].xx, &towns[i].yy);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:189:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &st[i].xx, &st[i].yy, &ed[i].xx, &ed[i].yy);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:271:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &b, &h);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4060 KB Output is correct
2 Correct 469 ms 30608 KB Output is correct
3 Correct 485 ms 29960 KB Output is correct
4 Correct 331 ms 22400 KB Output is correct
5 Correct 489 ms 32252 KB Output is correct
6 Correct 477 ms 30020 KB Output is correct
7 Correct 195 ms 20860 KB Output is correct
8 Correct 285 ms 33420 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2226 ms 140032 KB Output is correct
2 Correct 2220 ms 140672 KB Output is correct
3 Correct 2108 ms 140764 KB Output is correct
4 Correct 2106 ms 140892 KB Output is correct
5 Correct 550 ms 48440 KB Output is correct
6 Correct 535 ms 32200 KB Output is correct
7 Correct 2182 ms 140788 KB Output is correct
8 Correct 389 ms 54256 KB Output is correct
9 Correct 434 ms 54152 KB Output is correct
10 Correct 1180 ms 106812 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 718 ms 36740 KB Output is correct
2 Correct 682 ms 36004 KB Output is correct
3 Correct 721 ms 34120 KB Output is correct
4 Correct 524 ms 26488 KB Output is correct
5 Correct 688 ms 39340 KB Output is correct
6 Correct 792 ms 41600 KB Output is correct
7 Correct 768 ms 36468 KB Output is correct
8 Correct 727 ms 35816 KB Output is correct
9 Correct 404 ms 25588 KB Output is correct
10 Correct 714 ms 36920 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2655 ms 148108 KB Output is correct
2 Correct 1718 ms 93920 KB Output is correct
3 Correct 2631 ms 161528 KB Output is correct
4 Correct 757 ms 43860 KB Output is correct
5 Correct 2619 ms 151620 KB Output is correct
6 Correct 689 ms 48336 KB Output is correct
7 Correct 1974 ms 167324 KB Output is correct
8 Correct 2499 ms 166168 KB Output is correct
9 Correct 683 ms 73784 KB Output is correct
10 Correct 1324 ms 118480 KB Output is correct
11 Correct 721 ms 50172 KB Output is correct