Submission #140559

#	Time	Username	Problem	Language	Result	Execution time	Memory
140559		luciocf	Bridges (APIO19_bridges)	C++14	43 / 100	411 ms	6776 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int maxn = 1e5+10;
const int inf = 1e9+10;

struct Edge
{
	int u, v, w;
} edge[maxn], aux[1010];

struct Op
{
	int u, w, ind;
} query[maxn];

int n, m, q;
int tot;

int ans[maxn];

int pai[maxn], peso[maxn];

int tree[4*maxn];

vector<pii> grafo[maxn];

bool comp(Edge a, Edge b) {return a.w > b.w;}
bool comp2(Op a, Op b) {return a.w > b.w;}

void init(void)
{
	for (int i = 1; i <= n; i++)
	{
		pai[i] = i, peso[i] = 1;
		grafo[i].clear();
	}
}

int Find(int x)
{
	if (pai[x] == x) return x;
	return pai[x] = Find(pai[x]);
}

void Join(int x, int y)
{
	x = Find(x), y = Find(y);
	if (x == y) return;

	if (peso[x] < peso[y]) swap(x, y);

	pai[y] = x, peso[x] += peso[y];
}

void get_mst(void)
{
	init();

	for (int i = 1; i <= m; i++)
		aux[i] = edge[i];

	sort(aux+1, aux+m+1, comp);

	for (int i = 1; i <= m; i++)
	{
		if (Find(aux[i].u) != Find(aux[i].v))
		{
			Join(aux[i].u, aux[i].v);

			grafo[aux[i].u].push_back({aux[i].v, aux[i].w});
			grafo[aux[i].v].push_back({aux[i].u, aux[i].w});
		}
	}
}

void dfs(int u, int p, int w)
{
	tot++;

	for (auto v: grafo[u])
		if (v.first != p && v.second >= w)
			dfs(v.first, u, w);
}

void build(int node, int l, int r)
{
	if (l == r)
	{
		tree[node] = edge[l].w;
		return;
	}

	int mid = (l+r)>>1;

	build(2*node, l, mid); build(2*node+1, mid+1, r);

	tree[node] = min(tree[2*node], tree[2*node+1]);
}

void upd(int node, int l, int r, int pos, int v)
{
	if (l == r)
	{
		tree[node] = v;
		return;
	}

	int mid = (l+r)>>1;

	if (pos <= mid) upd(2*node, l, mid, pos, v);
	else upd(2*node+1, mid+1, r, pos, v);

	tree[node] = min(tree[2*node], tree[2*node+1]);
}

int busca1(int node, int l, int r, int pos, int v)
{
	if (tree[node] >= v || r <= pos) return inf;

	if (l == r) return l;

	int mid = (l+r)>>1;

	int p1 = busca1(2*node, l, mid, pos, v);
	if (p1 != inf) return p1;

	return busca1(2*node+1, mid+1, r, pos, v);
}

int busca2(int node, int l, int r, int pos, int v)
{
	if (tree[node] >= v || l >= pos) return inf;

	if (l == r) return l;

	int mid = (l+r)>>1;

	int p1 = busca2(2*node+1, mid+1, r, pos, v);
	if (p1 != inf) return p1;

	return busca2(2*node, l, mid, pos, v);
}

void solve_small(void)
{
	for (int i = 1; i <= q; i++)
	{
		int op;
		scanf("%d", &op);

		if (op == 1)
		{
			int ind, w;
			scanf("%d %d", &ind, &w);

			edge[ind].w = w;
		}
		else
		{
			int u, w;
			scanf("%d %d", &u, &w);

			get_mst();

			tot = 0;
			dfs(u, 0, w);

			printf("%d\n", tot);
		}
	}
}

void solve_chain(void)
{
	if (n > 1)
		build(1, 1, n-1);

	for (int i = 1; i <= q; i++)
	{
		int op;
		scanf("%d", &op);

		if (op == 1)
		{
			int ind, w;
			scanf("%d %d", &ind, &w);

			if (n > 1)
				upd(1, 1, n-1, ind, w);
		}
		else
		{
			int u, w;
			scanf("%d %d", &u, &w);

			if (n == 1)
			{
				printf("1\n");
				continue;
			}

			int r = busca1(1, 1, n-1, u-1, w);
			int l = busca2(1, 1, n-1, u, w);

			int ans = (r == inf ? n-u : r-u);

			ans += (l == inf ? u-1 : u-l-1);

			printf("%d\n", ans+1);
		}
	}
}

void solve_two(void)
{
	for (int i = 1; i <= q; i++)
	{
		int fuckyou;
		scanf("%d", &fuckyou);

		scanf("%d %d", &query[i].u, &query[i].w);
		query[i].ind = i;
	}

	sort(edge+1, edge+m+1, comp);
	sort(query+1, query+q+1, comp2);

	init();

	int p = 1;

	for (int i = 1; i <= q; i++)
	{
		while (edge[p].w >= query[i].w)
		{
			Join(edge[p].u, edge[p].v);
			p++;
		}

		ans[query[i].ind] = peso[Find(query[i].u)];
	}

	for (int i = 1; i <= q; i++)
		printf("%d\n", ans[i]);
}

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

	bool ok = 1;
	if (m != n-1) ok = 0;

	for (int i = 1; i <= m; i++)
	{
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);

		edge[i] = {u, v, w};

		if (v != i+1 || u != i) ok = 0;
	}

	scanf("%d", &q);
	
	if (n <= 1000 && m <= 1000 && q <= 10000)
	{
		solve_small();
		return 0;
	}

	if (ok)
	{
		solve_chain();
		return 0;
	}

	solve_two();
}

Compilation message (stderr)

bridges.cpp: In function 'void solve_small()':
bridges.cpp:153:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &op);
   ~~~~~^~~~~~~~~~~
bridges.cpp:158:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &ind, &w);
    ~~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:165:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &u, &w);
    ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp: In function 'void solve_chain()':
bridges.cpp:185:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &op);
   ~~~~~^~~~~~~~~~~
bridges.cpp:190:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &ind, &w);
    ~~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:198:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &u, &w);
    ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp: In function 'void solve_two()':
bridges.cpp:223:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &fuckyou);
   ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:225:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &query[i].u, &query[i].w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:253:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:261:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:268:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 0 / 17
• Subtask 4: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27