Submission #242083

#	Time	Username	Problem	Language	Result	Execution time	Memory
242083		mhy908	Bridges (APIO19_bridges)	C++14	13 / 100	3092 ms	8812 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()
#define svec(x) sort(x.begin(), x.end())
#define press(x) x.erase(unique(x.begin(), x.end()), x.end())
#define lb(x, v) lower_bound(x.begin(), x.end(), v)
#define ub(x, v) upper_bound(x.begin(), x.end(), v)
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=2000000000000000000;
const LL mod1=1000000007;
const LL mod2=998244353;
const int inf=2000000000;

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[50010];
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);
    //printf("connect %d to %d\n", b, a);
    sz[a]+=sz[b];
    par[b]=a;
    stk[++re]=mp(a, b);
}
inline void rollback(){
    int a=stk[re].F, b=stk[re].S;
    //printf("cut %d from %d\n", b, a);
    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=sqrt(q);
    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:67:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(; pv<noch.size(); pv++){
               ~~^~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:91: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:92: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:93:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
bridges.cpp:94: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: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27