제출 #249139

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
249139		crossing0ver	다리 (APIO19_bridges)	C++17	29 / 100	3074 ms	7544 KiB

bridges

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 5e4+5;
struct bridge{
	int a,b,val;
	bridge(){
		a = b = val = 0;
	}
};
int n,m,q;
bool vis[N];
vector<bridge> e;
vector< pair<int,int> > adj[N];
int dfs(int v,int val) {
	int cnt = 1;
	vis[v] = 1;
	for (auto i : adj[v]) {
		if (i.second >= val && !vis[i.first])
			cnt += dfs(i.first,val);
	}
	return cnt;
}
int arr[100009],t[400009];

void build(int v,int tl,int tr) {
	if (tl == tr) {
		t[v] = arr[tl];
		return;
	}
	int tm = (tl + tr)/2;
	build(v*2,tl,tm);
	build(v*2|1,tm+1,tr);
	t[v] = min(t[v*2],t[v*2+1]);
}
void upd(int v,int tl,int tr,int pos,int val) {
	if (tl == tr) {
		t[v] = arr[tl] = val;
		return;
	}
	int tm = (tl + tr)/2;
	if (pos <= tm)
		upd(v*2,tl,tm,pos,val);
	else 
		upd(v*2|1,tm+1,tr,pos,val);
	t[v] = min(t[v*2],t[v*2+1]);
}
int get(int v,int tl,int tr,int l,int r) {
	if (l > tr || r < tl) return INT_MAX;
	if (l <= tl && r >= tr) return t[v];
	int tm = (tl + tr)/2;
	return min( get(v*2,tl,tm,l,r),
				get(v*2|1,tm+1,tr,l,r));
}
void LINE() {
	for (int i = 1; i <= m; i++) {
		arr[i] = e[i].val;
	}
	build(1,1,m);
	for (int type,x,y;q--;) {
		cin >> type >> x >> y;
		if (type == 1) {
			upd(1,1,m,x,y);
		}
		else {
			int lo = x, hi = m;
			while (lo < hi) {
				int mid = (lo + hi + 1)/2;
				if (get(1,1,m,x,mid) >= y)
					lo = mid;
				else hi = mid-1;
			}
			int ans = 1;
			if (x != n && get(1,1,m,lo,lo) < y) lo--;
			if (x != n) ans += lo + 1 - x;
			lo = 1, hi = x-1;
			if (x != 1) {
			while (lo < hi) {
				int mid = (lo + hi)/2;
				if (get(1,1,m,mid,x-1) >= y)
					hi = mid;
				else lo = mid+1;
			}
			if (hi == 0 || get(1,1,m,hi,x-1) < y) hi++;
			ans += x - hi;
			}
			cout << ans <<'\n';
		}
	}
	
	
	exit(0);
}
main() {
	cin >> n >> m;
	e.resize(m+1);
	bool fl1 = (m == n-1);
	for (int i = 1; i <= m; i++) {
		cin >> e[i].a >> e[i].b >> e[i].val;
		if (e[i].a != i || e[i].b != i+1)
			fl1 = 0;
		adj[e[i].a].pb({e[i].b,e[i].val});
		adj[e[i].b].pb({e[i].a,e[i].val});
	}
	cin >> q;
	if (fl1 && n > 1) {
		LINE();
	}
	
	for (int type,x,y;q--;) {
		cin >> type >> x >> y;
		if (type == 1) {
			int a = e[x].a, b = e[x].b,val = e[x].val;
			adj[a].erase(find(adj[a].begin(),adj[a].end(),make_pair(b,val)));
			adj[b].erase(find(adj[b].begin(),adj[b].end(),make_pair(a,val)));
			e[x].val = y;
			adj[a].pb({b,y});
			adj[b].pb({a,y});
		}
		else {
			cout << dfs(x,y) <<'\n';
			fill(vis,vis+n+1,0);
		}
	}
	
}

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp:94:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

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