Submission #568843

#	Time	Username	Problem	Language	Result	Execution time	Memory
568843		birthdaycake	Bridges (APIO19_bridges)	C++17	43 / 100	981 ms	18752 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],seg[200001];
int N,Left,Right,Value;

void Update(){
    int ind = N + Left - 1;
    seg[ind] = Value;
    while(ind /= 2) seg[ind] = min(seg[ind * 2], seg[ind * 2 + 1]);
}


int Query(int l = 1, int r = N, int ind = 1){
    if(l > Right || r < Left) return 1e18;
    if(l >= Left && r <= Right) return seg[ind];
    int mid = (l + r) / 2;
    return min(Query(l, mid, ind * 2), Query(mid + 1, r, ind * 2 + 1));
    
}
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;
    if(m == n - 1){
        N = exp2(ceil(log2(m)));
        for(int i = 0; i < m; i++){
            int a,b,c; cin >> a >> b >> c;
            Left = Right = i + 1;
            Value = c;
            Update();
        }
        int q; cin >> q;
        for(int i = 0; i < q; i++){
            int t; cin >> t;
            if(t == 1){
                int p; cin >> p >> Value;
                Left = p;
                Update();
            }else{
                int s,w, ans = 1; cin >> s >> w;
                int l = s, r = m, a1 = 0;
                while(l <= r){
                    int mid = (l + r) / 2;
                    Left = s;
                    Right = mid;
                    if(Query() >= w){
                        a1 = mid - (s - 1);
                        l = mid + 1;
                    }else{
                        r = mid - 1;
                    }
                }
                ans += a1;
                l = 1; r = s - 1; a1 = 0;
                while(l <= r){
                    int mid = (l + r) / 2;
                    Right = s - 1;
                    Left = mid;
                    if(Query() >= w){
                        a1 = ((s - 1) - mid + 1);
                        r = mid - 1;
                    }else{
                        l = mid + 1;
                    }
                }
                cout << ans + a1 << endl;
            }
        }
        
        
        return 0;
    }
    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: 16 / 16
• Subtask 3: 0 / 17
• Subtask 4: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27