Submission #774684

#	Time	Username	Problem	Language	Result	Execution time	Memory
774684		That_Salamander	Bridges (APIO19_bridges)	C++14	13 / 100	3082 ms	14100 KiB

bridges

#include <bits/stdc++.h>
#define int long long

#define FOR(var,bound) for(int var = 0; var < bound; var++)
#define FORB(var,lb,ub) for (int var = lb; var < ub; var++)
#define FORR(var,bound) for(int var = bound-1; var >= 0; var--)

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

int n, m, q;
vector<pair<int, int>> conn[100000];
pair<pair<int, int>, pair<int, int>> edges[100000];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;

    FOR (i, m) {
        int u, v, d;
        cin >> u >> v >> d;

        u--; v--;

        edges[i] = {
            {u, conn[u].size()},
            {v, conn[v].size()}
        };

        conn[u].push_back({v, d});
        conn[v].push_back({u, d});
    }

    cin >> q;

    FOR(i, q) {
        int t;
        cin >> t;

        if (t == 1) {
            int b, r;
            cin >> b >> r;

            b--;

            conn[edges[b].first.first][edges[b].first.second].second = r;
            conn[edges[b].second.first][edges[b].second.second].second = r;
        } else {
            int s, w;
            cin >> s >> w;

            s--;

            vector<bool> visited(100000);
            queue<int> q;
            q.push(s);
            int res = 0;

            while (q.size()) {
                int x = q.front(); q.pop();
                if (visited[x])continue;
                visited[x] = true;
                res++;

                for (auto c: conn[x]) {
                    if (c.second >= w) {
                        q.push(c.first);
                    }
                }
            }


            cout << res << 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