Submission #255849

#	Time	Username	Problem	Language	Result	Execution time	Memory
255849		balbit	다리 (APIO19_bridges)	C++14	0 / 100	105 ms	4972 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

struct ev{
    int a,b,w; // a acts as s smtimes
    int id;
};
//struct qu{
//    int s,w,i;
//};
const int maxn = 5e4+100;
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;
    for (int i = 0 ;i<n; ++i) {
        par[i] = i, sz[i] = 1;
    }
    vector<ev> v;
    for (int i = 0; i<m; ++i) {
        int a,b,w; cin>>a>>b>>w;
        v.pb({a-1,b-1,w,-1});
    }
    int q; cin>>q;
    for (int i = 0; i<q; ++i) {
        int foo, s,w; cin>>foo>>s>>w;
        v.pb({s-1,-1,w,i});
    }
    sort(ALL(v), [&](ev a, ev b){return a.w!=b.w?a.w < b.w:a.id<b.id;});
    vector<int> qu(q);
    for (auto e : v) {
        if (e.id == -1) {
            merge(e.a, e.b);
        }else{
            qu[e.id] = sz[find(e.a)];
        }
    }
    for (int i = 0; i<q; ++i) {
        cout<<qu[i]<<endl;
    }
}

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