| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 933766 | irmuun | 다리 (APIO19_bridges) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
struct segtree{
ll n;
vector<ll>d;
vector<ll>u;
segtree(ll n):n(n){
d.resize(4*n);
build(1,0,n-1);
}
void build(ll node,ll l,ll r){
if(l==r){
d[node]=0;
return;
}
ll mid=(l+r)/2;
build(node*2,l,mid);
build(node*2+1,mid+1,r);
d[node]=min(d[node*2],d[node*2+1]);
}
ll query(ll node,ll l,ll r,ll L,ll R){
if(l > R || r < L || L > R){
return 1e18;
}
if(L <= l && r <= R){
return d[node];
}
ll mid=(l+r)/2;
return min(query(node*2,l,mid,L,R),query(node*2+1,mid+1,r,L,R));
}
void update(ll node,ll l,ll r,ll k,ll val){
if(l>k || r<k)return;
if(l==r){
d[node]=val;
return;
}
ll mid=(l+r)/2;
update(node*2,l,mid,k,val);
update(node*2+1,mid+1,r,k,val);
d[node]=min(d[node*2],d[node*2+1]);
}
};
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll n,m;
cin>>n>>m;
multiset<pair<ll,ll>>adj[n];
vector<array<ll,3>>edge;
for(ll i=0;i<m;i++){
ll u,v,d;
cin>>u>>v>>d;
u--,v--;
adj[u].insert({v,d});
adj[v].insert({u,d});
edge.pb({u,v,d});
}
vector<bool>used(n);
ll q;
cin>>q;
if(n<=1000&&m<=1000&&q<=10000){
while(q--){
ll t;
cin>>t;
if(t==1){
ll b,r;
cin>>b>>r;
b--;
auto [u,v,d]=edge[b];
adj[u].erase(adj[u].find({v,d}));
adj[v].erase(adj[v].find({u,d}));
edge[b][2]=r;
d=r;
adj[u].insert({v,d});
adj[v].insert({u,d});
}
else{
ll s,w;
cin>>s>>w;
s--;
fill(all(used),0);
function <void(ll)> dfs=[&](ll x){
used[x]=true;
for(auto [y,d]:adj[x]){
if(d>=w&&!used[y]){
dfs(y);
}
}
};
dfs(s);
ll ans=0;
for(ll i=0;i<n;i++){
if(used[i]==true){
ans++;
}
}
cout<<ans<<"\n";
}
}
return 0;
}
if(m==n-1){
segtree sg(n);
for(auto [u,v,d]:edge){
sg.update(1,0,n-1,min(u,v),d);
}
while(q--){
ll t;
cin>>t;
if(t==1){
ll b,r;
cin>>b>>r;
b--;
ll u=edge[b][0],v=edge[b][1];
sg.update(1,0,n-1,min(u,v),r);
}
else{
ll s,w;
cin>>s>>w;
s--;
ll l=0,r=s;
while(l<r){
ll mid=(l+r)/2;
if(sg.query(1,0,n-1,mid,s)>=w){
r=mid;
}
else{
l=mid+1;
}
}
ll ans=s-l+1;
ll l=s+1,r=n-1;
while(l<r){
ll mid=(l+r+1)/2;
if(sg.query(1,0,n-1,s,l-1)>=w){
l=mid;
}
else{
r=mid-1;
}
}
ans+=l-s;
cout<<ans<<"\n";
}
}
return 0;
}
}