Submission #1087234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087234		alexander707070	Bridges (APIO19_bridges)	C++14	100 / 100	1138 ms	17052 KiB

bridges

#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;

const int bucket_sz=500;

int n,m,q,type,s,w,ans[MAXN];
int a[MAXN],b[MAXN],c[MAXN],ori[MAXN];

struct query{
    int type,s,w,id;

    inline friend bool operator < (query fr,query sc){
        return fr.w<sc.w;
    }
};

bool cmp(query fr,query sc){
    return fr.id<sc.id;
}

struct edge{
    int a,b,c,id;

    inline friend bool operator <(edge fr,edge sc){
        if(fr.c!=sc.c)return fr.c>sc.c;
        return fr.id<sc.id;
    }
};

struct unionfind{
    int dsu[MAXN],sz[MAXN];

    void init(){
        for(int i=1;i<=n;i++){
            dsu[i]=i; sz[i]=1;
        }
    }

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

    void mergev(int x,int y){
        int rootx=root(x);
        int rooty=root(y);

        if(rootx==rooty)return;
        if(sz[rootx]<sz[rooty])swap(rootx,rooty);

        sz[rootx]+=sz[rooty];
        dsu[rooty]=rootx;
    }
}graph;

set<edge> e;

vector<query> z;
vector<query> updates,queries;
int li[MAXN],tim,vis[MAXN],tim2;

vector<int> g[MAXN];

int dfs(int x){
    vis[x]=tim2;
    int res=graph.sz[x];

    for(int i:g[x]){
        if(vis[i]==tim2)continue;
        res+=dfs(i);
    }

    return res;
}

void solve(){
    for(int i=1;i<=m;i++)ori[i]=c[i];

    updates.clear(); queries.clear();

    for(int i=0;i<z.size();i++){
        if(z[i].type==1)updates.push_back(z[i]);
        else queries.push_back(z[i]);
    }

    sort(queries.begin(),queries.end());
    sort(updates.begin(),updates.end(),cmp);

    tim++;
    for(int i=0;i<updates.size();i++){
        li[updates[i].s]=tim;
    }

    graph.init();
    auto it=e.begin();

    for(int i=queries.size()-1;i>=0;i--){

        while(it!=e.end()){
            edge curr=*it;
            if(curr.c>=queries[i].w){
                it++;

                if(li[curr.id]==tim){
                    continue;
                }
                graph.mergev(curr.a,curr.b);
            }else break;
        }

        for(query curr:updates){
            if(curr.id>queries[i].id)break;
            c[curr.s]=curr.w;
        }

        for(query curr:updates){
            if(c[curr.s]<queries[i].w)continue;
            if(graph.root(a[curr.s])==graph.root(b[curr.s]))continue;

            g[graph.root(a[curr.s])].push_back(graph.root(b[curr.s]));
            g[graph.root(b[curr.s])].push_back(graph.root(a[curr.s]));
        }

        tim2++;
        ans[queries[i].id]=dfs(graph.root(queries[i].s));

        for(query curr:updates){
            g[graph.root(a[curr.s])].clear();
            g[graph.root(b[curr.s])].clear();
        }

        for(query curr:updates){
            if(curr.id>queries[i].id)break;
            c[curr.s]=ori[curr.s];
        }
    }

    for(query curr:updates){
        e.erase({a[curr.s],b[curr.s],c[curr.s],curr.s});
        c[curr.s]=curr.w;
        e.insert({a[curr.s],b[curr.s],c[curr.s],curr.s});
    }
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i]>>b[i]>>c[i];
        e.insert({a[i],b[i],c[i],i});
    }

    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>type>>s>>w;
        z.push_back({type,s,w,i});

        if(z.size()==bucket_sz){
            solve(); z.clear();
        }
    }

    if(!z.empty()){
        solve(); z.clear();
    }

    for(int i=1;i<=q;i++){
        if(ans[i]>0)cout<<ans[i]<<"\n";
    }

    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void solve()':
bridges.cpp:83:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i=0;i<z.size();i++){
      |                 ~^~~~~~~~~
bridges.cpp:92:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(int i=0;i<updates.size();i++){
      |                 ~^~~~~~~~~~~~~~~

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