Submission #722183

#	Time	Username	Problem	Language	Result	Execution time	Memory
722183		Darren0724	Bridges (APIO19_bridges)	C++17	100 / 100	2549 ms	14756 KiB

bridges

#pragma GCC optimize("Ofast","O4","unroll-loops")
#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma")
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
#define endl '\n'

namespace {
const int N=200005;
vector<int> v[N];
int K=1100;
int n,m;
int pa[50005],sz[50005];
vector<pair<int,int>> rec;
void init(){
    rec.clear();
    for(int i=0;i<n;i++){
        pa[i]=i;
        sz[i]=1;
    }
}

int Find(int k){
    return (pa[k]==k?k:Find(pa[k]));
}
void onion(int a,int b){
    a=Find(a);
    b=Find(b);
    //cout<<a<<' '<<b<<endl;
    if(a==b){
        return;
    }
    if(sz[a]>sz[b]){
        swap(a,b);
    }
    //cout<<"onion "<<a<<' '<<b<<endl;
    rec.emplace_back(a,b);
    pa[a]=b;
    sz[b]+=sz[a];
}
void undo(){
    int a,b;
    tie(a,b)=rec.back();
    rec.pop_back();
    sz[b]-=sz[a];
    pa[a]=a;
}

void mangorz()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    rec.reserve(777771449);
    vector<int> a(m),b(m),c(m);
    vector<int> g;
    for(int i=0;i<m;i++){
        cin>>a[i]>>b[i]>>c[i];
        a[i]--;b[i]--;
        g.push_back(c[i]);
    }
    int q;cin>>q;
    vector<int> id(q),p(q),x(q);
    for(int i=0;i<q;i++){
        cin>>id[i]>>p[i]>>x[i];p[i]--;
        g.push_back(x[i]);
    }
    sort(all(g));
    g.resize(unique(all(g))-g.begin());
    for(int i=0;i<m;i++){
        c[i]=lower_bound(all(g),c[i])-g.begin();
    }
    for(int i=0;i<q;i++){
        x[i]=lower_bound(all(g),x[i])-g.begin();
    }
    vector<int> ans(q);

    for(int block=0;block<=q/K;block++){
        vector<int> vis(m);
        int s=K*block;
        int t=K*(block+1);
        t=min(t,q);
        vector<int> idx;
        for(int i=s;i<t;i++){
            if(id[i]==1){
                vis[p[i]]=1;  //modify
            }
            else{
                idx.push_back(i);  //ask
            }
        }
        // no
        for(int i=0;i<m;i++){
            if(vis[i]==0){
                v[c[i]].push_back(i);
            }
        }
        sort(all(idx),[&](int i,int j){return x[i]>x[j];});
        int ptr=N-1; // for add edge
        init();
        for(int j:idx){
            while(ptr>=x[j]){
                for(int k:v[ptr]){
                    onion(a[k],b[k]);
                }
                ptr--;
            }
            int rec1=rec.size();
            for(int i=j;i>=s;i--){
                if(id[i]==2){
                    continue;
                }
                if(vis[p[i]]==1){
                    vis[p[i]]=0;
                    if(x[j]<=x[i]){
                        onion(a[p[i]],b[p[i]]);
                    }
                }
            }
            for(int i=j;i<t;i++){
                if(id[i]==2){
                    continue;
                }
                if(vis[p[i]]==1){
                    vis[p[i]]=0;
                    if(x[j]<=c[p[i]]){
                        onion(a[p[i]],b[p[i]]);
                    }
                }
            }
            for(int i=s;i<t;i++){
                if(id[i]==1){
                    vis[p[i]]=1;
                }
            }

            ans[j]=sz[Find(p[j])];
            /*for(int i1=0;i1<n;i1++){
                cout<<pa[i1]<<' ';
            }
            cout<<endl;*/
            while(rec.size()>rec1){
                undo();
            }
        }
        for(int i=s;i<t;i++){
            if(id[i]==1){
                c[p[i]]=x[i];
            }
        }
        for(int i=0;i<m;i++){
            if(vis[i]==0){
                v[c[i]].clear();
            }
        }
    }
    for(int i=0;i<q;i++){
        if(ans[i]!=0){
            cout<<ans[i]<<endl;
        }
    }


}

}

int32_t main(){
    mangorz();
}

Compilation message (stderr)

bridges.cpp:2:76: warning: bad option '-favx' to pragma 'optimize' [-Wpragmas]
    2 | #pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma")
      |                                                                            ^
bridges.cpp:2:76: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
bridges.cpp:2:76: warning: bad option '-fsse' to pragma 'optimize' [-Wpragmas]
bridges.cpp:2:76: warning: bad option '-fsse2' to pragma 'optimize' [-Wpragmas]
bridges.cpp:2:76: warning: bad option '-fsse3' to pragma 'optimize' [-Wpragmas]
bridges.cpp:2:76: warning: bad option '-fssse3' to pragma 'optimize' [-Wpragmas]
bridges.cpp:2:76: warning: bad option '-fsse4' to pragma 'optimize' [-Wpragmas]
bridges.cpp:2:76: warning: bad option '-fpopcnt' to pragma 'optimize' [-Wpragmas]
bridges.cpp:2:76: warning: bad option '-fabm' to pragma 'optimize' [-Wpragmas]
bridges.cpp:2:76: warning: bad option '-fmmx' to pragma 'optimize' [-Wpragmas]
bridges.cpp:2:76: warning: bad option '-ffma' to pragma 'optimize' [-Wpragmas]
bridges.cpp:17:11: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   17 | void init(){
      |           ^
bridges.cpp:17:11: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
bridges.cpp:17:11: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
bridges.cpp:17:11: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
bridges.cpp:17:11: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:17:11: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:17:11: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
bridges.cpp:17:11: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
bridges.cpp:17:11: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
bridges.cpp:17:11: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
bridges.cpp:17:11: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
bridges.cpp:25:15: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   25 | int Find(int k){
      |               ^
bridges.cpp:25:15: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
bridges.cpp:25:15: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
bridges.cpp:25:15: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
bridges.cpp:25:15: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:25:15: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:25:15: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
bridges.cpp:25:15: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
bridges.cpp:25:15: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
bridges.cpp:25:15: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
bridges.cpp:25:15: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
bridges.cpp:28:23: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   28 | void onion(int a,int b){
      |                       ^
bridges.cpp:28:23: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
bridges.cpp:28:23: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
bridges.cpp:28:23: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
bridges.cpp:28:23: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:28:23: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:28:23: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
bridges.cpp:28:23: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
bridges.cpp:28:23: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
bridges.cpp:28:23: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
bridges.cpp:28:23: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
bridges.cpp:43:11: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   43 | void undo(){
      |           ^
bridges.cpp:43:11: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
bridges.cpp:43:11: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
bridges.cpp:43:11: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
bridges.cpp:43:11: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:43:11: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:43:11: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
bridges.cpp:43:11: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
bridges.cpp:43:11: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
bridges.cpp:43:11: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
bridges.cpp:43:11: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
bridges.cpp:51:14: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   51 | void mangorz()
      |              ^
bridges.cpp:51:14: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
bridges.cpp:51:14: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
bridges.cpp:51:14: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
bridges.cpp:51:14: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:51:14: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:51:14: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
bridges.cpp:51:14: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
bridges.cpp:51:14: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
bridges.cpp:51:14: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
bridges.cpp:51:14: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
bridges.cpp: In function 'void {anonymous}::mangorz()':
bridges.cpp:100:38: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
  100 |         sort(all(idx),[&](int i,int j){return x[i]>x[j];});
      |                                      ^
bridges.cpp:100:38: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
bridges.cpp:100:38: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
bridges.cpp:100:38: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
bridges.cpp:100:38: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:100:38: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:100:38: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
bridges.cpp:100:38: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
bridges.cpp:100:38: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
bridges.cpp:100:38: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
bridges.cpp:100:38: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
bridges.cpp:144:29: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  144 |             while(rec.size()>rec1){
      |                   ~~~~~~~~~~^~~~~
bridges.cpp: At global scope:
bridges.cpp:170:14: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
  170 | int32_t main(){
      |              ^
bridges.cpp:170:14: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
bridges.cpp:170:14: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
bridges.cpp:170:14: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
bridges.cpp:170:14: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:170:14: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:170:14: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
bridges.cpp:170:14: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
bridges.cpp:170:14: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
bridges.cpp:170:14: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
bridges.cpp:170:14: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]

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