Submission #934022

#	Time	Username	Problem	Language	Result	Execution time	Memory
934022		vjudge1	Bridges (APIO19_bridges)	C++14	13 / 100	3061 ms	25424 KiB

bridges

#include <bits/stdc++.h>
#include <vector>
using namespace std;
struct tpos
{
	int u, w, x;
};
struct edge
{
	int u, v, w;
};
vector<tpos> adj[1<<19];
edge edges[1<<19];
int visi[1<<19]; int iter = 1;
void dfs(int nodo, int &coche, int &ret)
{
	visi[nodo] = iter; ret++;
	for (tpos t: adj[nodo])
	{
		if (visi[t.u] == iter) continue;
		if (t.w < coche) continue;
		dfs(t.u, coche, ret);
	}
}
int main() 
{
	int n, m; cin >> n >> m;
	int a, b, w;
	for (int i = 1; i <= m; i++)
	{
		cin >> a >> b >> w;
		adj[a].push_back({b, w, i});
		adj[b].push_back({a, w, i});
		edges[i] = {a, b, w};
	}
	int q; cin >> q;
	int tipo;
	while (q--)
	{
		cin >> tipo;
		iter++;
		if (tipo & 1)
		{
			cin >> a >> b;
			edges[a].w = b;
			int u = edges[a].u; int v = edges[a].v;

			for (tpos &e: adj[u])
				if (e.x == a)
				{
					e.w = b;
					break;
				}
			for (tpos &e: adj[v])
				if (e.x == a)
				{
					e.w = b;
					break;
				}
			continue;
		}
		cin >> a >> b;
		int ret = 0;
		dfs(a, b, ret);
		cout << ret << '\n';
	}
}

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