Submission #207824

#	Time	Username	Problem	Language	Result	Execution time	Memory
207824		Segtree	Bridges (APIO19_bridges)	C++14	13 / 100	211 ms	632 KiB

bridges

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#define N 1010
vector<ll> to[N],cost[N];
bool vis[N];
ll cmp;
void dfs(ll x,ll lim){
	if(vis[x])return;
	vis[x]=1;
	cmp++;
	for(int i=0;i<to[x].size();i++){
		if(cost[x][i]>=lim)dfs(to[x][i],lim);
	}
}
ll a[N],b[N],c[N];
int main(){
	ll n,m,q;
	cin>>n>>m; if(n>1000)return 0;
	rep(i,m){
		cin>>a[i]>>b[i]>>c[i];
	}
	cin>>q;
	while(q--){
		ll t,x,y;
		cin>>t>>x>>y;
		if(t==1){
			x--;
			c[x]=y;
		}
		if(t==2){
			for(int i=1;i<=n;i++){
				vis[i]=0;
				to[i].clear();
				cost[i].clear();
			}
			rep(i,m){
				to[a[i]].push_back(b[i]);
				to[b[i]].push_back(a[i]);
				cost[a[i]].push_back(c[i]);
				cost[b[i]].push_back(c[i]);
			}
			cmp=0;
			dfs(x,y);
			cout<<cmp<<endl;
		}
	}
}

Compilation message (stderr)

bridges.cpp: In function 'void dfs(ll, ll)':
bridges.cpp:21:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<to[x].size();i++){
              ~^~~~~~~~~~~~~

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