Submission #655109

#	Time	Username	Problem	Language	Result	Execution time	Memory
655109		DeMen100ns	Bridges (APIO19_bridges)	C++17	14 / 100	221 ms	13104 KiB

bridges

/*
Author : DeMen100ns (a.k.a Vo Khac Trieu)
School : VNU-HCM High school for the Gifted
fuck you adhoc
*/

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
const long long INF = 1e18 + 7;
const int MAXA = 1e9;
const int B = sqrt(N) + 5;

int n, m, q, p[N], siz[N], ans[N];
vector <pair<int, int>> a[N];
array<int, 3> edge[N], qu[N];
bool f[N];

void dfs(int u, int val){
    f[u] = true;
    for(pair<int, int> st : a[u]){
        int i = st.first, w = st.second;
        if (f[i] || w < val) continue;

        dfs(i, val);
    }
}

int root(int u){
    if (u == p[u]) return u;
    else return p[u] = root(p[u]);
}

inline void Union(int u, int v){
    u = root(u); v = root(v);
    if (u == v) return;

    if (siz[u] < siz[v]) swap(u, v);
    p[v] = u;
    siz[u] += siz[v];
}

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int u, v, w; cin >> u >> v >> w;
        a[u].push_back({v, w});
        a[v].push_back({u, w});

        edge[i] = {w, u, v};
    }

    cin >> q;
    for(int i = 1; i <= q; ++i){
        int type, u, val; cin >> type >> u >> val;
        qu[i] = {val, u, i};
    }
    sort(edge + 1, edge + m + 1, greater<array<int, 3>>());
    sort(qu + 1, qu + q + 1, greater<array<int, 3>>());

    for(int i = 1; i <= n; ++i){
        p[i] = i; siz[i] = 1;
    }

    int j = 1;
    for(int i = 1; i <= q; ++i){
        while(j <= m && edge[j][0] >= qu[i][0]){
            Union(edge[j][1], edge[j][2]);
            ++j;
        }
        ans[qu[i][2]] = siz[root(qu[i][1])];
    }
    for(int i = 1; i <= q; ++i) cout << ans[i] << endl;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // freopen("codeforces.inp","r",stdin);
    // freopen("codeforces.out","w",stdout);

    int t = 1; // cin >> t;
    while (t--)
    {
        solve();
    }
}

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