Submission #690502

#	Time	Username	Problem	Language	Result	Execution time	Memory
690502		kieuphat159	Bridges (APIO19_bridges)	C++14	0 / 100	96 ms	61504 KiB

bridges

// 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 = 5e3+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;
}

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