Submission #568731

#	Time	Username	Problem	Language	Result	Execution time	Memory
568731		shrimb	다리 (APIO19_bridges)	C++17	13 / 100	92 ms	676 KiB

bridges

#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;

#define int long long
#define endl '\n'
#define mod 1000000007
//\
#define mod 1686876991

const int maxn = 1001;

vector<pair<int,int>> adj[maxn];
int w[maxn];

int dsu[maxn];
int sz[maxn];

int Find (int x) {
    return dsu[x] == x ? x : dsu[x] = Find(dsu[x]);
}

void Union (int a, int b) {
    int x = Find(a), y = Find(b);
    if (x==y) return;
    sz[y] += sz[x];
    dsu[x] = y;
}

signed main () {
    cin.tie(0)->sync_with_stdio(0);

    int n, m;
    cin >> n >> m;

    for (int i = 0 ; i < m ; i++) {
        int u, v, x;
        cin >> u >> v >> x;
        adj[u].emplace_back(v, i + 1);
        adj[v].emplace_back(u, i + 1);
        w[i + 1] = x;
    }

    int q;
    cin >> q;
    if (n <= 1000 and m <= 1000 and q <= 10000) {
        while (q--) {
            int t;
            cin >> t;
            if (t == 1) {
                int b, r;
                cin >> b >> r;
                w[b] = r;
            } else {
                int s, wj;
                cin >> s >> wj;
                for (int i = 1 ; i <= n ; i++) dsu[i] = i, sz[i] = 1;
                for (int i = 1 ; i <= n ; i++) for (auto [j, b] : adj[i]) if (w[b] >= wj) Union(i, j);
                cout << sz[Find(s)] << endl;
            }
        }
    }
}

Compilation message (stderr)

bridges.cpp:17:1: warning: multi-line comment [-Wcomment]
   17 | //\
      | ^

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