Submission #241159

#	Time	Username	Problem	Language	Result	Execution time	Memory
241159		gs13105	간선 파괴 (GA5_destroy)	C++17	60 / 100	2576 ms	26648 KiB

destroy

#include <bits/stdc++.h>
using namespace std;

int par[710];
int root(int x)
{
	return x == par[x] ? x : (par[x] = root(par[x]));
}
bool merge(int x, int y)
{
	x = root(x);
	y = root(y);
	if(x == y)
		return 0;

	par[x] = y;
	return 1;
}

pair<int, int> edg[150000];

vector<pair<int, int>> seg[270000];
void init(int x, int l, int r)
{
	if(l == r)
	{
		seg[x].push_back(edg[l]);
		return;
	}

	init(2 * x, l, (l + r) / 2);
	init(2 * x + 1, (l + r) / 2 + 1, r);

	for(auto [a, b] : seg[2 * x])
	{
		par[a] = a;
		par[b] = b;
	}
	for(auto [a, b] : seg[2 * x + 1])
	{
		par[a] = a;
		par[b] = b;
	}

	for(auto [a, b] : seg[2 * x])
		if(merge(a, b))
			seg[x].push_back({ a, b });
	for(auto [a, b] : seg[2 * x + 1])
		if(merge(a, b))
			seg[x].push_back({ a, b });
}
int get_val(int x, int l, int r, int s, int g)
{
	if(g < l || r < s || g < s)
		return 0;

	if(s <= l && r <= g)
	{
		int c = 0;
		for(auto [a, b] : seg[x])
			if(merge(a, b))
				c++;

		return c;
	}

	return get_val(2 * x, l, (l + r) / 2, s, g) + get_val(2 * x + 1, (l + r) / 2 + 1, r, s, g);
}

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		edg[i] = { x, y };
	}

	init(1, 1, m);

	int q;
	scanf("%d", &q);
	for(int i = 0; i < q; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);

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

		int r = n - get_val(1, 1, m, 1, x - 1) - get_val(1, 1, m, y + 1, m);
		printf("%d\n", r);
	}

	return 0;
}

Compilation message (stderr)

destroy.cpp: In function 'int main()':
destroy.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
destroy.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~
destroy.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
destroy.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 0 / 40