Submission #934022

#TimeUsernameProblemLanguageResultExecution timeMemory
934022vjudge1Bridges (APIO19_bridges)C++14
13 / 100
3061 ms25424 KiB
#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';
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...