Submission #675852

#	Time	Username	Problem	Language	Result	Execution time	Memory
675852		Dan4Life	Bridges (APIO19_bridges)	C++17	0 / 100	124 ms	208704 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second

const int maxn = (int)1e3+10;

int n, m, q;
vector<int> adj[maxn];
unordered_map<int,int> wei[maxn];
int vis[maxn], tc;
unordered_map<int,multiset<int>> S[maxn];
struct query{
	int t, x, y;
} Q[maxn];

struct e{
	int a, b, w;
} e[maxn];

void dfs(int s, int weight, int p){
	vis[s]=tc;
	for(auto u : adj[s]){
		int w = wei[min(s,u)][max(s,u)];
		if(u==p or weight>w or vis[u]==tc) continue;
		dfs(u,weight,s);
	}
}

int32_t main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		cin >> e[i].a >> e[i].b >> e[i].w;
		int &a = e[i].a, &b = e[i].b, &w = e[i].w; if(a>b) swap(a,b);
		if(!wei[a].count(b)) wei[a][b]=w;
		else wei[a][b]=max(w,wei[a][b]);
		S[a][b].insert(w);
		adj[a].pb(b); adj[b].pb(a);
	}
	cin >> q;
	for(int i = 1; i <= q; i++){
		cin >> Q[i].t >> Q[i].x >> Q[i].y; tc=i;
		if(Q[i].t==1){
			int j = Q[i].x; 
			int &a = e[j].a, &b = e[j].b, &w = e[j].w;
			S[a][b].erase(S[a][b].find(w)); S[a][b].insert(Q[i].y);
			wei[a][b]=*prev(S[a][b].end());
		}
		else{
			dfs(Q[i].x, Q[i].y, -1); int cnt = 0;
			for(int i = 1; i <= n; i++) cnt+=(vis[i]==tc);
			cout << cnt << "\n";
		}
	}
}

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