Submission #978561

#	Time	Username	Problem	Language	Result	Execution time	Memory
978561		akacool445k	Bridges (APIO19_bridges)	C++14	13 / 100	3092 ms	18656 KiB

bridges

#include <bits/stdc++.h>
 
using namespace std;
#define ff first
#define ss second
// #define int long long
const long long mod = 1e9 + 7;
const long long shrek = (1 << 30);
const int gay = 5e4 + 10;
set<pair<pair<int, int>, int>> adj[gay];
bool vis[gay];
vector<int> cur;
void dfs(int x, int w) {
    vis[x] = 1;
    cur.push_back(x);
    for(auto y : adj[x]) {
        if(vis[y.ff.ff] == 1 || y.ff.ss < w) {
            continue;
        }
        dfs(y.ff.ff, w);
    }
}
signed main() {
    int n, m, q;
    cin >> n >> m; 
    int u[m + 5], v[m + 5], w[m + 5];
    for(int i = 1; i <= m; i++) {
        cin >> u[i] >> v[i] >> w[i];
        adj[u[i]].insert({{v[i], w[i]}, i});
        adj[v[i]].insert({{u[i], w[i]}, i});

    }
    cin >> q;
    while(q--) {
        int c, st, f;
        cin >> c >> st >> f;
        if(c == 1) {
            adj[u[st]].erase({{v[st], w[st]}, st});
            adj[v[st]].erase({{u[st], w[st]}, st});
            w[st] = f;
            adj[u[st]].insert({{v[st], w[st]}, st});
            adj[v[st]].insert({{u[st], w[st]}, st});
        } else {
            cur.clear();
            dfs(st, f);
            for(int x : cur) vis[x] = 0;
            cout << cur.size() << '\n';
        }
    }
    return 0;
}

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