Submission #568831

#	Time	Username	Problem	Language	Result	Execution time	Memory
568831		birthdaycake	Bridges (APIO19_bridges)	C++17	27 / 100	240 ms	17292 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],dsu[200001],sz[200001],ans[200001];


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

void Union(int a, int b){
    a = Find(a); b = Find(b);
    if(sz[a] > sz[b]) swap(a,b);
    dsu[a] = b;
    sz[b] += sz[a];
}
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;
    if(n <= 1000 && m <= 1000 && q <= 10000){
        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;
            }
        }
        return 0;
    }
    vector<pair<int,pair<int,int>>>qw(q);
    for(int i = 0; i < q; i++){
        cin >> qw[i].first >> qw[i].second.first >> qw[i].second.second;
        swap(qw[i].first,qw[i].second.second);
        qw[i].second.second = i;
    }
    sort(qw.begin(), qw.end(), greater<pair<int,pair<int,int>>>());
    for(int i = 0; i < m; i++){
        swap(edg[i].first,edg[i].second.second);
    }
    sort(edg.begin(), edg.end(), greater<pair<int,pair<int,int>>>());
    for(int i = 1; i <= n; i++){
        dsu[i] = i;
        sz[i] = 1;
    }
    int j = 0;
    for(int i = 0; i < q; i++){
        int a = qw[i].second.first, c = qw[i].first;
        while(j < m && edg[j].first >= c){
            if(Find(edg[j].second.first) != Find(edg[j].second.second)) Union(edg[j].second.first, edg[j].second.second);
            j++;
        }
        ans[qw[i].second.second] = sz[Find(a)];
    }
    for(int i = 0; i < q; i++){
        cout << ans[i] << 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: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27