Submission #255772

# Submission time Handle Problem Language Result Execution time Memory
255772 2020-08-01T20:07:30 Z mehrdad_sohrabi Bridges (APIO19_bridges) C++14
13 / 100
2267 ms 8172 KB
#include <bits/stdc++.h>
typedef int ll;
typedef long double ld;
#define pb push_back
#define pii pair < int , int >
#define F first
#define S second
//#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=5e4+100,sq=750;
vector <pair <int,pii > > yy;
bool vis[N];
bool vis2[N];
ll par[N],sz[N];
ll getpar(ll v){
    if (par[v]==v) return v;
    return par[v]=getpar(par[v]);
}
inline void mrg(ll v,ll u){
    ll u1=getpar(u),v1=getpar(v);
    if (u1==v1) return ;
    if (sz[u1]>sz[v1])swap(u1,v1);
    par[u1]=v1;
    sz[v1]+=sz[u1];
}
ll pp[N],zz[N];
ll gg(ll v){
    if (pp[v]==v) return v;
    return pp[v]=gg(pp[v]);
}
inline void merg(ll v,ll u){
    ll v1=gg(v),u1=gg(u);
    if (v1==u1) return ;
    if (zz[u1]>zz[v1]) swap(v1,u1);
    pp[u1]=v1;
    zz[v1]+=zz[u1];
}
ll ans[N];
vector <pair <int,pii> > q;
int32_t main(){
    sync;
    ll n,m;
    scanf("%d %d",&n,&m);
    for (int i=1;i<=m;i++){
        ll u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        yy.pb({w,{u,v}});
    }
    ll q1;
    scanf("%d",&q1);
    while(q1--){
        ll u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        q.pb({u,{v,w}});
    }
    for (int i=0;i<q.size();i+=sq){
        memset(vis,0,sizeof vis);
        memset(vis2,0,sizeof vis2);
        vector <pii> g;
        vector <pair <int,pii> > yal;
        for (int j=i;j<min(i+sq,(int)q.size());j++){
            if (q[j].F==1) vis[q[j].S.F-1]=1;
            else{
                g.pb({q[j].S.S,j});
            }
        }
        memset(par,0,sizeof par);
        memset(sz,0,sizeof sz);
        for (int j=1;j<=n;j++){
            sz[j]=1;
            par[j]=j;
        }
        for (int j=0;j<yy.size();j++){
            if (vis[j]) continue;
            yal.pb(yy[j]);
        }
        sort(yal.begin(),yal.end());
        sort(g.begin(),g.end());
        reverse(g.begin(),g.end());
        ll cnt=0;
        for (int j=yal.size()-1;j>-1;j--){
            while(cnt<g.size() && g[cnt].F>yal[j].F){
                for (int k=i;k<min(i+sq,(ll)q.size());k++){
                    if (q[k].F==1){
                        vis2[q[k].S.F-1]=0;
                        ll v=yy[q[k].S.F-1].S.F,u=yy[q[k].S.F-1].S.S;
                        pp[v]=getpar(v);
                        pp[u]=getpar(u);
                        zz[pp[v]]=sz[pp[v]];
                        zz[pp[u]]=sz[pp[u]];
                        pp[pp[v]]=pp[v];
                        pp[pp[u]]=pp[u];
                    }
                    else{
                        ll v=q[k].S.F;
                        pp[v]=getpar(v);
                        zz[pp[v]]=sz[pp[v]];
                        pp[pp[v]]=pp[v];
                    }
                }
                ll id=g[cnt].S;
                for (int k=id;k>=i;k--){
                    if (q[k].F==2) continue;
                    ll v=yy[q[k].S.F-1].S.F,u=yy[q[k].S.F-1].S.S;
                    if (vis2[q[k].S.F-1]) continue;
                    vis2[q[k].S.F-1]=1;
                    if (q[k].S.S>=g[cnt].F){
                        merg(u,v);
                    }
                }
                for (int k=id+1;k<min(i+sq,(ll)q.size());k++){
                    if (q[k].F==2) continue;
                    ll v=yy[q[k].S.F-1].S.F,u=yy[q[k].S.F-1].S.S;
                    if (vis2[q[k].S.F-1]) continue;
                    vis2[q[k].S.F-1]=1;
                    if (yy[q[k].S.F-1].F>=g[cnt].F){
                        merg(u,v);
                    }
                }
                ans[id]=zz[gg(q[id].S.F)];
                cnt++;
            }

            mrg(yal[j].S.F,yal[j].S.S);
        }
        while(cnt<g.size()){
                for (int k=i;k<min(i+sq,(ll)q.size());k++){
                    if (q[k].F==1){
                        vis2[q[k].S.F-1]=0;
                        ll v=yy[q[k].S.F-1].S.F,u=yy[q[k].S.F-1].S.S;
                        pp[v]=getpar(v);
                        pp[u]=getpar(u);
                        zz[pp[v]]=sz[pp[v]];
                        zz[pp[u]]=sz[pp[u]];
                        pp[pp[u]]=pp[u];
                        pp[pp[v]]=pp[v];
                    }
                    else{
                        ll v=q[k].S.F;
                        pp[v]=getpar(v);
                        zz[pp[v]]=sz[pp[v]];
                        pp[pp[v]]=pp[v];
                    }
                }
                ll id=g[cnt].S;
                for (int k=id;k>=i;k--){
                    if (q[k].F==2) continue;
                    ll v=yy[q[k].S.F-1].S.F,u=yy[q[k].S.F-1].S.S;
                    if (vis2[q[k].S.F-1]) continue;
                    vis2[q[k].S.F-1]=1;
                    if (q[k].S.S>=g[cnt].F){
                        merg(u,v);
                    }
                }
                for (int k=id+1;k<min(i+sq,(ll)q.size());k++){
                    if (q[k].F==2) continue;
                    ll v=yy[q[k].S.F-1].S.F,u=yy[q[k].S.F-1].S.S;
                    if (vis2[q[k].S.F-1]) continue;
                    vis2[q[k].S.F-1]=1;
                    if (yy[q[k].S.F-1].F>=g[cnt].F){
                        merg(u,v);
                    }
                }
                ans[id]=zz[gg(q[id].S.F)];
                cnt++;
        }
        for (int j=i;j<(min(i+sq,(ll)q.size()));j++){
            if (q[j].F==1){
                yy[q[j].S.F-1].F=q[j].S.S;
            }
        }
    }
    for (int i=0;i<q.size();i++){
        if (q[i].F==2)
        printf("%d \n",ans[i]);
    }
}



Compilation message

bridges.cpp: In function 'int32_t main()':
bridges.cpp:60:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<q.size();i+=sq){
                  ~^~~~~~~~~
bridges.cpp:77:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0;j<yy.size();j++){
                      ~^~~~~~~~~~
bridges.cpp:86:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(cnt<g.size() && g[cnt].F>yal[j].F){
                   ~~~^~~~~~~~~
bridges.cpp:130:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(cnt<g.size()){
               ~~~^~~~~~~~~
bridges.cpp:177:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<q.size();i++){
                  ~^~~~~~~~~
bridges.cpp:47: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:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&u,&v,&w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~
bridges.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q1);
     ~~~~~^~~~~~~~~~
bridges.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&u,&v,&w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 85 ms 1348 KB Output is correct
4 Correct 39 ms 1276 KB Output is correct
5 Correct 71 ms 1220 KB Output is correct
6 Correct 68 ms 1220 KB Output is correct
7 Correct 69 ms 1220 KB Output is correct
8 Correct 73 ms 1340 KB Output is correct
9 Correct 65 ms 1220 KB Output is correct
10 Correct 73 ms 1220 KB Output is correct
11 Correct 74 ms 1220 KB Output is correct
12 Correct 71 ms 1220 KB Output is correct
13 Correct 79 ms 1220 KB Output is correct
14 Correct 77 ms 1220 KB Output is correct
15 Correct 77 ms 1400 KB Output is correct
16 Correct 67 ms 1220 KB Output is correct
17 Correct 69 ms 1220 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 2267 ms 4868 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1886 ms 3840 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 90 ms 8172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2267 ms 4868 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 85 ms 1348 KB Output is correct
4 Correct 39 ms 1276 KB Output is correct
5 Correct 71 ms 1220 KB Output is correct
6 Correct 68 ms 1220 KB Output is correct
7 Correct 69 ms 1220 KB Output is correct
8 Correct 73 ms 1340 KB Output is correct
9 Correct 65 ms 1220 KB Output is correct
10 Correct 73 ms 1220 KB Output is correct
11 Correct 74 ms 1220 KB Output is correct
12 Correct 71 ms 1220 KB Output is correct
13 Correct 79 ms 1220 KB Output is correct
14 Correct 77 ms 1220 KB Output is correct
15 Correct 77 ms 1400 KB Output is correct
16 Correct 67 ms 1220 KB Output is correct
17 Correct 69 ms 1220 KB Output is correct
18 Incorrect 2267 ms 4868 KB Output isn't correct
19 Halted 0 ms 0 KB -