| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 690500 | kieuphat159 | Bridges (APIO19_bridges) | C++14 | 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.
// Template //
#include <bits/stdc++.h>
#define FOR(i, a, b) for(ll i=a; i<=b; i++)
#define FORD(i, a, b) for(ll i=a; i>=b; i--)
#define pb push_back
#define ALL(a) a.begin(), a.end()
#define mp make_pair
#define fi first
#define se second
#define mset(a, b) memset(a, b, sizeof(a))
#define BIT(x, i) ((x>>i)&1)
#define MASK(i) (1LL<<(i))
#define all(a, n) a+1, a+1+n
using namespace std;
typedef int64_t ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef pair<ll, ii> iii;
const ll maxn = 5e4+5;
const ll mod = 1e9+7;
const ll inf = 1e18;
const ll base = 37;
const ld eps = 1e-10;
template<class T>
bool minimize(T &a, T b){
return a>b ? a=b, true : false;
}
template<class T>
bool maximize(T &a, T b){
return a<b ? a=b, true : false;
}
ll POW(ll a, ll b)
{
if (b==0) return 1;
if (b==1) return a;
ll tmp=POW(a, b/2) % mod;
return b%2==0 ? (tmp * tmp)%mod : (((tmp*tmp)%mod)*a)%mod;
}
// Main Function //
ll n, m, d[maxn][maxn];
vector<ll>ds[maxn];
ii b[maxn];
bool vis[maxn];
void input()
{
cin>>n>>m;
FOR(i, 1, m)
{
ll u, v, c; cin>>u>>v>>c;
ds[u].pb(v);
ds[v].pb(u);
d[u][v] = d[v][u] = c;
b[i] = {u, v};
}
}
ll bfs(ll s, ll w)
{
ll cnt = 1;
queue<ll>q;
mset(vis, false);
vis[s] = true;
q.push(s);
while(!q.empty())
{
ll u = q.front();
q.pop();
for(ll v:ds[u])
{
if (vis[v]) continue;
ll c = d[u][v];
if (c < w) continue;
q.push(v);
cnt++;
vis[v] = true;
}
}
return cnt;
}
void sub1()
{
ll q; cin>>q;
while(q--)
{
ll t; cin>>t;
if (t==1) {
ll f, s; cin>>f>>s;
ll u = b[f].fi, v = b[f].se;
d[u][v] = s;
d[v][u] = s;
} else {
ll s, w; cin>>s>>w;
cout<<bfs(s, w)<<'\n';
}
}
}
void solve()
{
if (n<=1000) return void(sub1());
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
#define task "BAI3"
// freopen(task".INP", "r", stdin);
// freopen(task".OUT", "w", stdout);
int test_case=1; //cin>>test_case;
while(test_case--)
{
input(), solve();
cout<<'\n';
}
return 0;
}