Submission #255852

#	Time	Username	Problem	Language	Result	Execution time	Memory
255852		balbit	Bridges (APIO19_bridges)	C++14	13 / 100	3091 ms	2284 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

#define ll long long

#define pll pair<ll, ll>
#define f first
#define s second

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<" "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x ){ cerr<<x<<endl; }
template<typename T, typename ...S> void _do(T && x , S&&...y){ cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT

const int maxn = 5e4+100;

//vector<pii> g[maxn];

struct ed{
    int a,b,w;
};
int par[maxn], sz[maxn];
int find(int x) {return x == par[x]? x : par[x] = find(par[x]);}
void merge(int a, int b) {
    a = find(a), b = find(b);
    if (a==b)return;
    sz[b] += sz[a];
    par[a] = b;
}
signed main(){
    IOS();
    int n,m; cin>>n>>m;
    vector<ed> v;
    for (int i = 0; i<m; ++i) {
        int a,b,w; cin>>a>>b>>w;
        --a; --b;
        v.pb({a,b,w});

    }
    int q; cin>>q;
    for (int i = 0; i<q; ++i) {
        int foo, s,w; cin>>foo>>s>>w; --s;
        if (foo == 1) {
            v[s].w = w;
        }else{
            for (int j = 0; j<n; ++j) par[j] = j, sz[j] = 1;
            for (ed &e : v) {
                if (e.w >= w) {
                    merge(e.a,e.b);
                }
            }
            cout<<sz[find(s)]<<endl;
        }
    }
}

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