Submission #545253

#	Time	Username	Problem	Language	Result	Execution time	Memory
545253		amunduzbaev	Bridges (APIO19_bridges)	C++17	13 / 100	59 ms	2644 KiB

bridges

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

#define ar array

namespace sub1{
const int N = 5e4 + 5;
vector<int> edges[N];

void solve(int n, int m, int q, vector<ar<int, 3>>& e){
	while(q--){
		int t; cin>>t;
		if(t == 1){
			int j, w; cin>>j>>w;
			e[--j][2] = w;
		} else {
			int a, w; cin>>a>>w;
			for(int i=0;i<m;i++){
				if(e[i][2] >= w){
					edges[e[i][0]].push_back(e[i][1]);
					edges[e[i][1]].push_back(e[i][0]);
				}
			}
			
			int cnt = 0;
			vector<int> used(n + 1);
			function<void(int)> dfs = [&](int u){
				used[u] = 1, cnt++;
				for(auto x : edges[u]){
					if(!used[x]) dfs(x);
				}
			};
			dfs(a);
			cout<<cnt<<"\n";
			for(int i=1;i<=n;i++) edges[i].clear();
		}
	}
}

};

namespace sub2{

const int B = 230;
int mn[B];

void solve(int n, int m, int q, vector<ar<int, 3>>& e){
	vector<int> a(m);
	for(int i=0;i<m;i++){
		a[--e[i][0]] = e[i][2];
	}
	
	for(int b=0;b<B;b++){
		int l = b * B, r = min((b + 1) * B, m);
		mn[b] = 1e9;
		for(int j=l;j<r;j++){
			//~ mn[j] = 
		}
	}
	
	while(q--){
		
	}
}

};

signed main(){
	ios::sync_with_stdio(0); cin.tie(0); 
	
	int n, m; cin>>n>>m;
	vector<ar<int, 3>> e(m);
	bool is = 1;
	for(int i=0;i<m;i++){
		int a, b, c; cin>>a>>b>>c;
		e[i] = {a, b, c};
		if(a != i + 1 || b != i + 2) is = 0;
	}
	
	int q; cin>>q;
	if(n <= 1000 && m <= 1000 && q <= 10000){
		sub1::solve(n, m, q, e);
		return 0;
	}
	
	if(is){
		sub2::solve(n, m, q, e);
	} else {
		
	}
}

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