Submission #568753

#	Time	Username	Problem	Language	Result	Execution time	Memory
568753		birthdaycake	Bridges (APIO19_bridges)	C++17	13 / 100	3082 ms	13148 KiB

bridges

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define mod 1000000007
#define boost ios_base::sync_with_stdio(false), cin.tie(NULL);
using namespace std;
 
 

vector<pair<int,int>>adj[200001];
int vs[200001];

signed main() {
 
    int n,m; cin >> n >> m;
    vector<pair<int,pair<int,int>>>edg(m);
    for(int i = 0; i < m; i++){
        int a,b,c; cin >> a >> b >> c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
        edg[i] = {a,{b,c}};
    }
    
    int q; cin >> q;
    while(q--){
        int t; cin >> t;
        if(t == 1){
            int x,y; cin >> x >> y;
            x--;
            int a = edg[x].first, b = edg[x].second.first, c = edg[x].second.second, cnt = 0;
            for(auto s: adj[a]){
                if(s.first == b && s.second == c){
                    auto u = adj[a].back();
                    if(s != adj[a].back()) {
                        adj[a].back().first = s.first;
                        adj[a].back().second = s.second;
                        adj[a][cnt].first = u.first;
                        adj[a][cnt].second = u.second;
                        
                    }
                    adj[a].pop_back();
                    adj[a].push_back({b,y});
                    break;
                }
                cnt++;
            }
            cnt = 0;
            for(auto s: adj[b]){
                if(s.first == a && s.second == c){
                    auto u = adj[b].back();
                    if(s != adj[b].back()){
                        adj[b].back().first = s.first;
                        adj[b].back().second = s.second;
                        adj[b][cnt].first = u.first;
                        adj[b][cnt].second = u.second;
                    }
                    adj[b].pop_back();
                    adj[b].push_back({a,y});
                    break;
                }
                cnt++;
            }
            edg[x] = {a,{b,y}};
        }else{
            int s,w, ans = 1; cin >> s >> w;
            queue<int>d;
            for(int i = 1; i <= n; i++) vs[i] = 0;
            vs[s] = 1;
            d.push(s);
            while(d.size()){
                auto y = d.front();
                d.pop();
                for(auto s:adj[y]){
                    if(s.second >= w){
                        if(!vs[s.first]){
                            ans++;
                            vs[s.first] = 1;
                            d.push(s.first);
                        }
                    }
                }
            }
            cout << ans << endl;
        }
    }
 
    /*
7 8
1 2 5
1 6 5
2 3 5
2 7 5
3 4 5
4 5 5
5 6 5
6 7 5
     
     
     
     3 4
     1 2 5
     2 3 2
     3 1 4
     2 3 8
     */
    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