제출 #545254

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
545254		amunduzbaev	다리 (APIO19_bridges)	C++17	29 / 100	201 ms	5160 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];
	}
	
	auto rec = [&](int b){
		int l = b * B, r = min((b + 1) * B, m);
		mn[b] = 1e9;
		for(int j=l;j<r;j++){
			mn[b] = min(mn[b], a[j]);
		}
	};
	
	for(int b=0;b<B;b++){
		rec(b);
	}
	
	while(q--){
		int t; cin>>t;
		if(t == 1){
			int i, w; cin>>i>>w;
			a[--i] = w;
			rec(i / B);
		} else {
			int i, w; cin>>i>>w, i--;
			int b = i / B;
			int lx = -1, rx = m;
			for(int j = b * B; j < i;j++){
				if(a[j] < w) lx = max(lx, j);
			}
			
			for(int j=i;j<min(m, (b + 1) * B);j++){
				if(a[j] < w) rx = min(rx, j);
			}
			
			for(int j=b-1;~j;j--){
				if(mn[j] >= w) continue;
				for(int l=j*B;l<(j+1)*B;l++){
					if(a[l] < w) lx = max(lx, l);
				} break;
			}
			
			for(int j=b+1;j<B;j++){
				if(mn[j] >= w) continue;
				for(int l=j*B;l<min(m, (j+1)*B);l++){
					if(a[l] < w) rx = min(rx, l);
				} break;
			}
			
			cout<<rx - lx<<"\n";
		}
	}
}

};

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: 16 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27