답안 #255773

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
255773 2020-08-01T20:08:44 Z mehrdad_sohrabi 다리 (APIO19_bridges) C++14
59 / 100
3000 ms 8388 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*2];
bool vis2[N*2];
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*2];
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);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 87 ms 1476 KB Output is correct
4 Correct 41 ms 1344 KB Output is correct
5 Correct 71 ms 1348 KB Output is correct
6 Correct 67 ms 1348 KB Output is correct
7 Correct 70 ms 1348 KB Output is correct
8 Correct 72 ms 1408 KB Output is correct
9 Correct 67 ms 1336 KB Output is correct
10 Correct 71 ms 1468 KB Output is correct
11 Correct 72 ms 1432 KB Output is correct
12 Correct 75 ms 1540 KB Output is correct
13 Correct 82 ms 1404 KB Output is correct
14 Correct 83 ms 1424 KB Output is correct
15 Correct 86 ms 1348 KB Output is correct
16 Correct 71 ms 1348 KB Output is correct
17 Correct 71 ms 1340 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2298 ms 6240 KB Output is correct
2 Correct 2373 ms 6188 KB Output is correct
3 Correct 2392 ms 6632 KB Output is correct
4 Correct 2425 ms 6520 KB Output is correct
5 Correct 2544 ms 6308 KB Output is correct
6 Correct 2789 ms 6200 KB Output is correct
7 Correct 2840 ms 6384 KB Output is correct
8 Correct 2792 ms 6476 KB Output is correct
9 Correct 412 ms 4180 KB Output is correct
10 Correct 2207 ms 6680 KB Output is correct
11 Correct 2190 ms 6584 KB Output is correct
12 Correct 2417 ms 6600 KB Output is correct
13 Correct 1462 ms 6780 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1836 ms 5484 KB Output is correct
2 Correct 1314 ms 4524 KB Output is correct
3 Correct 1928 ms 5736 KB Output is correct
4 Correct 1931 ms 5356 KB Output is correct
5 Correct 388 ms 4200 KB Output is correct
6 Correct 1873 ms 5484 KB Output is correct
7 Correct 1757 ms 5596 KB Output is correct
8 Correct 1691 ms 5736 KB Output is correct
9 Correct 1686 ms 5704 KB Output is correct
10 Correct 1568 ms 5868 KB Output is correct
11 Correct 959 ms 5300 KB Output is correct
12 Correct 926 ms 5484 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2782 ms 8388 KB Output is correct
2 Correct 400 ms 3572 KB Output is correct
3 Correct 265 ms 5920 KB Output is correct
4 Correct 303 ms 5796 KB Output is correct
5 Execution timed out 3047 ms 8008 KB Time limit exceeded
6 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 2298 ms 6240 KB Output is correct
2 Correct 2373 ms 6188 KB Output is correct
3 Correct 2392 ms 6632 KB Output is correct
4 Correct 2425 ms 6520 KB Output is correct
5 Correct 2544 ms 6308 KB Output is correct
6 Correct 2789 ms 6200 KB Output is correct
7 Correct 2840 ms 6384 KB Output is correct
8 Correct 2792 ms 6476 KB Output is correct
9 Correct 412 ms 4180 KB Output is correct
10 Correct 2207 ms 6680 KB Output is correct
11 Correct 2190 ms 6584 KB Output is correct
12 Correct 2417 ms 6600 KB Output is correct
13 Correct 1462 ms 6780 KB Output is correct
14 Correct 1836 ms 5484 KB Output is correct
15 Correct 1314 ms 4524 KB Output is correct
16 Correct 1928 ms 5736 KB Output is correct
17 Correct 1931 ms 5356 KB Output is correct
18 Correct 388 ms 4200 KB Output is correct
19 Correct 1873 ms 5484 KB Output is correct
20 Correct 1757 ms 5596 KB Output is correct
21 Correct 1691 ms 5736 KB Output is correct
22 Correct 1686 ms 5704 KB Output is correct
23 Correct 1568 ms 5868 KB Output is correct
24 Correct 959 ms 5300 KB Output is correct
25 Correct 926 ms 5484 KB Output is correct
26 Correct 2294 ms 6304 KB Output is correct
27 Correct 2448 ms 6056 KB Output is correct
28 Correct 2401 ms 6480 KB Output is correct
29 Correct 2092 ms 6132 KB Output is correct
30 Correct 2620 ms 6232 KB Output is correct
31 Correct 2633 ms 6216 KB Output is correct
32 Correct 2643 ms 6252 KB Output is correct
33 Correct 2472 ms 6388 KB Output is correct
34 Correct 2497 ms 6164 KB Output is correct
35 Correct 2476 ms 6192 KB Output is correct
36 Correct 2169 ms 6312 KB Output is correct
37 Correct 2163 ms 6240 KB Output is correct
38 Correct 2153 ms 6100 KB Output is correct
39 Correct 1922 ms 6244 KB Output is correct
40 Correct 1870 ms 6316 KB Output is correct
41 Correct 1867 ms 6036 KB Output is correct
42 Correct 1333 ms 5976 KB Output is correct
43 Correct 1365 ms 6068 KB Output is correct
44 Correct 1325 ms 6024 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 87 ms 1476 KB Output is correct
4 Correct 41 ms 1344 KB Output is correct
5 Correct 71 ms 1348 KB Output is correct
6 Correct 67 ms 1348 KB Output is correct
7 Correct 70 ms 1348 KB Output is correct
8 Correct 72 ms 1408 KB Output is correct
9 Correct 67 ms 1336 KB Output is correct
10 Correct 71 ms 1468 KB Output is correct
11 Correct 72 ms 1432 KB Output is correct
12 Correct 75 ms 1540 KB Output is correct
13 Correct 82 ms 1404 KB Output is correct
14 Correct 83 ms 1424 KB Output is correct
15 Correct 86 ms 1348 KB Output is correct
16 Correct 71 ms 1348 KB Output is correct
17 Correct 71 ms 1340 KB Output is correct
18 Correct 2298 ms 6240 KB Output is correct
19 Correct 2373 ms 6188 KB Output is correct
20 Correct 2392 ms 6632 KB Output is correct
21 Correct 2425 ms 6520 KB Output is correct
22 Correct 2544 ms 6308 KB Output is correct
23 Correct 2789 ms 6200 KB Output is correct
24 Correct 2840 ms 6384 KB Output is correct
25 Correct 2792 ms 6476 KB Output is correct
26 Correct 412 ms 4180 KB Output is correct
27 Correct 2207 ms 6680 KB Output is correct
28 Correct 2190 ms 6584 KB Output is correct
29 Correct 2417 ms 6600 KB Output is correct
30 Correct 1462 ms 6780 KB Output is correct
31 Correct 1836 ms 5484 KB Output is correct
32 Correct 1314 ms 4524 KB Output is correct
33 Correct 1928 ms 5736 KB Output is correct
34 Correct 1931 ms 5356 KB Output is correct
35 Correct 388 ms 4200 KB Output is correct
36 Correct 1873 ms 5484 KB Output is correct
37 Correct 1757 ms 5596 KB Output is correct
38 Correct 1691 ms 5736 KB Output is correct
39 Correct 1686 ms 5704 KB Output is correct
40 Correct 1568 ms 5868 KB Output is correct
41 Correct 959 ms 5300 KB Output is correct
42 Correct 926 ms 5484 KB Output is correct
43 Correct 2782 ms 8388 KB Output is correct
44 Correct 400 ms 3572 KB Output is correct
45 Correct 265 ms 5920 KB Output is correct
46 Correct 303 ms 5796 KB Output is correct
47 Execution timed out 3047 ms 8008 KB Time limit exceeded
48 Halted 0 ms 0 KB -