답안 #255782

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
255782 2020-08-01T20:27:25 Z mehrdad_sohrabi 다리 (APIO19_bridges) C++14
30 / 100
3000 ms 22552 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=400;
vector <pair <int,pii > > yy,yal[N*4];
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;
vector <int> com;
map <int,int> mp;

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);
        com.pb(w);
        yy.pb({w,{u,v}});
    }
    ll q1;
    scanf("%d",&q1);
    while(q1--){
        ll u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        com.pb(w);
        q.pb({u,{v,w}});
    }
    sort(com.begin(),com.end());
    for (int i=0;i<com.size();i++) mp[com[i]]=i;
    for (int i=0;i<yy.size();i++){
        yy[i].F=mp[yy[i].F];
    }
    for (int i=0;i<q.size();i++){
        q[i].S.S=mp[q[i].S.S];
    }
    for (int i=0;i<q.size();i+=sq){
        memset(vis,0,sizeof vis);
        memset(vis2,0,sizeof vis2);
        vector <pii> g;
        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 i=0;i<N*4;i++) yal[i].clear();
        for (int j=0;j<yy.size();j++){
            if (vis[j]) continue;
            yal[yy[j].F].pb(yy[j]);
        }
        sort(g.begin(),g.end());
        reverse(g.begin(),g.end());
        ll cnt=0;
        for (int j=N*4-1;j>-1;j--){
            while(cnt<g.size() && g[cnt].F>j){
                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++;
            }
            for (int jj=0;jj<yal[j].size();jj++){
                mrg(yal[j][jj].S.F,yal[j][jj].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:66:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<com.size();i++) mp[com[i]]=i;
                  ~^~~~~~~~~~~
bridges.cpp:67:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<yy.size();i++){
                  ~^~~~~~~~~~
bridges.cpp:70:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<q.size();i++){
                  ~^~~~~~~~~
bridges.cpp:73:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<q.size();i+=sq){
                  ~^~~~~~~~~
bridges.cpp:90:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0;j<yy.size();j++){
                      ~^~~~~~~~~~
bridges.cpp:98:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(cnt<g.size() && g[cnt].F>j){
                   ~~~^~~~~~~~~
bridges.cpp:139:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int jj=0;jj<yal[j].size();jj++){
                           ~~^~~~~~~~~~~~~~
bridges.cpp:143:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(cnt<g.size()){
               ~~~^~~~~~~~~
bridges.cpp:190:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<q.size();i++){
                  ~^~~~~~~~~
bridges.cpp:50: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:53: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:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q1);
     ~~~~~^~~~~~~~~~
bridges.cpp:61: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 4 ms 5632 KB Output is correct
2 Correct 4 ms 5632 KB Output is correct
3 Correct 91 ms 6504 KB Output is correct
4 Correct 61 ms 6392 KB Output is correct
5 Correct 83 ms 6272 KB Output is correct
6 Correct 69 ms 6016 KB Output is correct
7 Correct 72 ms 5980 KB Output is correct
8 Correct 74 ms 6356 KB Output is correct
9 Correct 67 ms 6108 KB Output is correct
10 Correct 75 ms 6364 KB Output is correct
11 Correct 72 ms 6364 KB Output is correct
12 Correct 73 ms 6364 KB Output is correct
13 Correct 83 ms 6400 KB Output is correct
14 Correct 82 ms 6368 KB Output is correct
15 Correct 81 ms 6488 KB Output is correct
16 Correct 69 ms 5980 KB Output is correct
17 Correct 73 ms 5980 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2573 ms 19100 KB Output is correct
2 Correct 2628 ms 19240 KB Output is correct
3 Execution timed out 3003 ms 19048 KB Time limit exceeded
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 2273 ms 17664 KB Output is correct
2 Correct 1127 ms 13908 KB Output is correct
3 Correct 1936 ms 16504 KB Output is correct
4 Correct 1985 ms 17572 KB Output is correct
5 Correct 503 ms 12832 KB Output is correct
6 Correct 1945 ms 17728 KB Output is correct
7 Correct 1952 ms 17672 KB Output is correct
8 Correct 1890 ms 17584 KB Output is correct
9 Correct 1670 ms 16672 KB Output is correct
10 Correct 1578 ms 16552 KB Output is correct
11 Correct 1661 ms 18824 KB Output is correct
12 Correct 1405 ms 18856 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3071 ms 22552 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 2573 ms 19100 KB Output is correct
2 Correct 2628 ms 19240 KB Output is correct
3 Execution timed out 3003 ms 19048 KB Time limit exceeded
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5632 KB Output is correct
2 Correct 4 ms 5632 KB Output is correct
3 Correct 91 ms 6504 KB Output is correct
4 Correct 61 ms 6392 KB Output is correct
5 Correct 83 ms 6272 KB Output is correct
6 Correct 69 ms 6016 KB Output is correct
7 Correct 72 ms 5980 KB Output is correct
8 Correct 74 ms 6356 KB Output is correct
9 Correct 67 ms 6108 KB Output is correct
10 Correct 75 ms 6364 KB Output is correct
11 Correct 72 ms 6364 KB Output is correct
12 Correct 73 ms 6364 KB Output is correct
13 Correct 83 ms 6400 KB Output is correct
14 Correct 82 ms 6368 KB Output is correct
15 Correct 81 ms 6488 KB Output is correct
16 Correct 69 ms 5980 KB Output is correct
17 Correct 73 ms 5980 KB Output is correct
18 Correct 2573 ms 19100 KB Output is correct
19 Correct 2628 ms 19240 KB Output is correct
20 Execution timed out 3003 ms 19048 KB Time limit exceeded
21 Halted 0 ms 0 KB -