Submission #732978

#	Time	Username	Problem	Language	Result	Execution time	Memory
732978		Magikarp4000	Bridges (APIO19_bridges)	C++17	0 / 100	97 ms	18788 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int MAXN = 5e4+1;
int n,m,q;
vector<PII> v[MAXN];
int p[MAXN], sz[MAXN], res[MAXN];
vector<pair<int,PII>> e;
vector<pair<PII,int>> qu;

int finds(int a) {
  if (p[a] != a) p[a] = finds(p[a]);
  return p[a];
}

void unite(int a, int b) {
  a = finds(a);
  b = finds(b);
  if (a != b) {
    if (sz[a] < sz[b]) swap(a,b);
    p[b] = a;
    sz[a] += sz[b];
  }
}

signed main() {
    OPTM;
    cin >> n >> m;
    FOR(i,0,m) {
        int a,b,w; cin >> a >> b >> w;
        v[a].PB({b,w});
        v[b].PB({a,w});
        e.PB({w,{a,b}});
    }
    sort(ALL(e),greater<pair<int,PII>>());
    cin >> q;
    FOR(i,0,q) {
        int w,s; cin >> w >> s;
        qu.PB({{w,s},i});
    }
    FOR(i,1,n+1) {
        p[i] = i;
        sz[i] = 1;
    }
    sort(ALL(qu),greater<pair<PII,int>>());
    int j = 0;
    FOR(i,0,q) {
        int w = qu[i].F.F, s = qu[i].F.S, idx = qu[i].S;
        while (j < m && e[j].F >= w) {
            unite(e[j].S.F, e[j].S.S);
            j++;
        }
        res[idx] = sz[finds(s)];
    }
    FOR(i,0,q) cout << res[i] << ln;
}

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