Submission #207822

#	Time	Username	Problem	Language	Result	Execution time	Memory
207822		Segtree	Bridges (APIO19_bridges)	C++14	0 / 100	5 ms	376 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];
		to[a[i]].push_back(b[i]);
		cost[a[i]].push_back(c[i]);
		to[b[i]].push_back(a[i]);
		cost[b[i]].push_back(c[i]);
	}
	cin>>q;
	while(q--){
		ll t,x,y;
		cin>>t>>x>>y;
		if(t==1){
			x--;
			for(int i=0;i<to[a[x]].size();i++){
				if(to[a[x]][i]==b[x]){
					cost[a[x]][i]=y;
				}
			}
			for(int i=0;i<to[b[x]].size();i++){
				if(to[b[x]][i]==a[x]){
					cost[b[x]][i]=y;
				}
			}
		}
		if(t==2){
			for(int i=1;i<=n;i++)vis[i]=0;
			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++){
              ~^~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:42:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<to[a[x]].size();i++){
                ~^~~~~~~~~~~~~~~~
bridges.cpp:47:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<to[b[x]].size();i++){
                ~^~~~~~~~~~~~~~~~

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