Submission #242085

#	Time	Username	Problem	Language	Result	Execution time	Memory
242085		mhy908	Bridges (APIO19_bridges)	C++14	100 / 100	2355 ms	9332 KiB

bridges

#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef pair<int, int> pii;
int n, m, q, sq;
pair<pii, int> ed[100010];
pair<int, pii> qu[100010];

pii stk[100010];
int par[50010], sz[50010], re, ans[100010];
inline void init(){for(int i=1; i<=50000; i++)par[i]=i, sz[i]=1; re=0;}
int findpar(int num){return num==par[num]?num:findpar(par[num]);}
inline void mergepar(int a, int b){
    a=findpar(a);
    b=findpar(b);
    if(a==b)return;
    if(sz[a]<sz[b])swap(a, b);
    sz[a]+=sz[b];
    par[b]=a;
    stk[++re]=mp(a, b);
}
inline void rollback(){
    int a=stk[re].F, b=stk[re].S;
    re--;
    par[b]=b;
    sz[a]-=sz[b];
}

bool ch[100010];
vector<pii> noch, query;
vector<int> ych;
inline void do_query(int s, int e){
    noch.clear(); query.clear(); ych.clear();
    memset(ch, 0, sizeof ch);
    init();
    for(int i=s; i<=e; i++){
        if(qu[i].F==2)query.eb(qu[i].S.S, i);
        else ch[qu[i].S.F]=true;
    }
    for(int i=1; i<=m; i++){
        if(!ch[i])noch.eb(ed[i].S, i);
        else ych.eb(i);
    }
    sort(all(query), greater<pii>());
    sort(all(noch), greater<pii>());
    int pv=0;
    for(auto i:query){
        for(; pv<noch.size(); pv++){
            if(noch[pv].F<i.F)break;
            mergepar(ed[noch[pv].S].F.F, ed[noch[pv].S].F.S);
        }
        int tmp=re;
        for(int j=i.S; j>=s; j--){
            if(qu[j].F==1&&ch[qu[j].S.F]){
                ch[qu[j].S.F]=false;
                if(qu[j].S.S>=i.F)mergepar(ed[qu[j].S.F].F.F, ed[qu[j].S.F].F.S);
            }
        }
        for(auto j:ych){
            if(ch[j]&&ed[j].S>=i.F)mergepar(ed[j].F.F, ed[j].F.S);
            ch[j]=true;
        }
        ans[i.S]=sz[findpar(qu[i.S].S.F)];
        while(re>tmp)rollback();
    }
    for(int i=s; i<=e; i++){
        if(qu[i].F==1)ed[qu[i].S.F].S=qu[i].S.S;
    }
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++)scanf("%d %d %d", &ed[i].F.F, &ed[i].F.S, &ed[i].S);
    scanf("%d", &q);
    for(int i=1; i<=q; i++)scanf("%d %d %d", &qu[i].F, &qu[i].S.F, &qu[i].S.S);
    sq=800;
    for(int st=1; st<=q; st+=sq){
        int fin=min(q, st+sq-1);
        do_query(st, fin);
    }
    for(int i=1; i<=q; i++){
        if(qu[i].F==2)printf("%d\n", ans[i]);
    }
}

Compilation message (stderr)

bridges.cpp: In function 'void do_query(int, int)':
bridges.cpp:52:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(; pv<noch.size(); pv++){
               ~~^~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:77:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1; i<=m; i++)scanf("%d %d %d", &ed[i].F.F, &ed[i].F.S, &ed[i].S);
                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
bridges.cpp:79:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1; i<=q; i++)scanf("%d %d %d", &qu[i].F, &qu[i].S.F, &qu[i].S.S);
                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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