Submission #872332

#	Time	Username	Problem	Language	Result	Execution time	Memory
872332		ttamx	Bridges (APIO19_bridges)	C++14	73 / 100	3031 ms	10312 KiB

bridges

#include<bits/stdc++.h>

using namespace std;

const int N=50005;
const int M=1e5+5;
const int Q=1e5+5;
const int K=320;

int n,m,q;
int ans[Q];

struct Edge{
    int u,v,w;
    bool operator<(const Edge &o){
        return w>o.w;
    }
}ed[M];

struct Query{
    int t,s,w;
    bool operator<(const Query &o){
        return w>o.w;
    }
}qr[Q];

struct DSU{
    int p[N],sz[N];
    stack<pair<int,int>> s;
    void init(){
        for(int i=1;i<=n;i++)p[i]=i,sz[i]=1;
        while(!s.empty())s.pop();
    }
    int fp(int u){
        return p[u]==u?u:fp(p[u]);
    }
    bool uni(int u,int v){
        u=fp(u),v=fp(v);
        if(u==v)return false;
        if(sz[u]<sz[v])swap(u,v);
        p[v]=u;
        sz[u]+=sz[v];
        s.emplace(u,v);
        return true;
    }
    int state(){
        return s.size();
    }
    void undo(int t){
        while(s.size()>t){
            auto [u,v]=s.top();
            s.pop();
            p[v]=v;
            sz[u]-=sz[v];
        }
    }
    int size(int u){
        return sz[fp(u)];
    }
}dsu;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for(int i=1;i<=m;i++)cin >> ed[i].u >> ed[i].v >> ed[i].w;
    cin >> q;
    for(int i=1;i<=q;i++)cin >> qr[i].t >> qr[i].s >> qr[i].w;
    for(int l=1,r=K;l<=q;l+=K,r+=K){
        r=min(r,q);
        dsu.init();
        set<int> upd;
        for(int i=l;i<=r;i++)if(qr[i].t==1)upd.emplace(qr[i].s);
        vector<Edge> def;
        for(int i=1;i<=m;i++)if(upd.find(i)==upd.end())def.emplace_back(ed[i]);
        sort(def.rbegin(),def.rend());
        vector<tuple<int,int,vector<int>>> qrs;
        for(int i=l;i<=r;i++){
            if(qr[i].t==1){
                ed[qr[i].s].w=qr[i].w;
            }else{
                vector<int> res;
                for(auto j:upd)if(ed[j].w>=qr[i].w)res.emplace_back(j);
                qrs.emplace_back(qr[i].w,i,res);
            }
        }
        sort(qrs.rbegin(),qrs.rend());
        for(auto [w,i,v]:qrs){
            while(!def.empty()&&def.back().w>=qr[i].w){
                dsu.uni(def.back().u,def.back().v);
                def.pop_back();
            }
            int st=dsu.state();
            for(auto j:v)dsu.uni(ed[j].u,ed[j].v);
            ans[i]=dsu.size(qr[i].s);
            dsu.undo(st);
        }
    }
    for(int i=1;i<=q;i++)if(qr[i].t==2)cout << ans[i] << "\n";
}

Compilation message (stderr)

bridges.cpp: In member function 'void DSU::undo(int)':
bridges.cpp:50:23: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         while(s.size()>t){
      |               ~~~~~~~~^~
bridges.cpp:51:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |             auto [u,v]=s.top();
      |                  ^
bridges.cpp: In function 'int main()':
bridges.cpp:87:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |         for(auto [w,i,v]:qrs){
      |                  ^

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