Submission #721528

#	Time	Username	Problem	Language	Result	Execution time	Memory
721528		victor_gao	Bridges (APIO19_bridges)	C++17	100 / 100	2955 ms	15888 KiB

bridges

#pragma GCC optimize("Ofast,unroll-loops,O3")
#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define pii pair<int,int>
#define x first
#define y second
#define N 50015
#define M 100015
#define B 500
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
struct dsu_data{
    int a,sz1,b,sz2;
    dsu_data(int _a,int _sz1,int _b,int _sz2):a(_a),sz1(_sz1),b(_b),sz2(_sz2){}
};
struct dsu{
    int boss[N],sz[N];
    stack<dsu_data>st;
    void init(int n){
        for (int i=0;i<=n+2;i++){
            boss[i]=i; sz[i]=1;
        }
        while (!st.empty()) st.pop();
    }
    int find(int x){
        if (boss[x]==x) return x;
        return find(boss[x]);
    }
    void Merge(int a,int b){
        int u=find(a),v=find(b);
        st.push(dsu_data(u,sz[u],v,sz[v]));
        if (u==v) return;
        if (sz[u]<sz[v]) swap(u,v);
        boss[v]=u;
        sz[u]+=sz[v];
    }
    void rollback(){
        if (st.empty()) return;
        dsu_data np=st.top(); st.pop();
        if (np.a==np.b) return;
        boss[np.a]=np.a;
        sz[np.a]=np.sz1;
        boss[np.b]=np.b;
        sz[np.b]=np.sz2;
    }
    void undo(int t){
        while (st.size()>t)
            rollback();
    }
}dsu;
struct Query{
    int type,a,b;
    Query(int x,int y,int z):type(x),a(y),b(z){}
};
struct Edge{
    int u,v,c,i;
    bool operator<(const Edge a)const{
        if (c!=a.c) return c>a.c;
        return i<a.i;
    }
};
vector<Query>qry;
vector<pii>now;
vector<int>have_use,op[M];
Edge E[M];
set<Edge>all;
int n,m,q,ans[M];
bool vis[M];
bool cmp(pii a,pii b){
    if (a.x!=b.x) return a.x>b.x;
    return a.y<b.y;
}
void solve(){
    auto it=all.begin();
    for (auto [c,id]:now){
        int pos=qry[id].a;
        while (it!=all.end()&&(*it).c>=c){
            dsu.Merge((*it).u,(*it).v);
            it++;
        }
        int t=dsu.st.size();
        for (auto i:have_use){
            int last=-1e9;
            for (auto j:op[i]){
                if (j<=id)
                    last=qry[j].b;
                else break;
            }
            if (last<0){
                if (E[i].c>=c)
                    dsu.Merge(E[i].u,E[i].v);
            }
            else if (last>=c)
                dsu.Merge(E[i].u,E[i].v);
        }
        ans[id]=dsu.sz[dsu.find(pos)];
        dsu.undo(t);
    }
}
signed main(){
    fast
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        cin>>E[i].u>>E[i].v>>E[i].c;
        E[i].i=i;
        all.insert(E[i]);
    }
    cin>>q;
    for (int i=1;i<=q;i++){
        int x,y,z; cin>>x>>y>>z;
        qry.emplace_back(Query(x,y,z));
    }
    for (int i=0;i<q;i+=B){
        for (int j=i;j<min(B+i,q);j++){
            if (qry[j].type==1){
                int e=qry[j].a;
                op[e].push_back(j);
                if (!vis[e]){
                    vis[e]=1;
                    have_use.emplace_back(e);
                    all.erase(E[e]);
                }
            }
            else now.emplace_back(pii(qry[j].b,j));
        }
        dsu.init(n);
        sort(now.begin(),now.end(),cmp);
        solve();
        for (auto i:have_use){
            int last=op[i].back();
            E[i].c=qry[last].b;
            all.insert(E[i]);
            op[i].clear();
            vis[i]=0;
        }
        have_use.clear();
        now.clear();
    }
    for (int i=0;i<q;i++){
        if (qry[i].type==2)
            cout<<ans[i]<<'\n';
    }
}

Compilation message (stderr)

bridges.cpp:2:88: warning: bad option '-favx' to pragma 'optimize' [-Wpragmas]
    2 | #pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
      |                                                                                        ^
bridges.cpp:2:88: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
bridges.cpp:2:88: warning: bad option '-fsse' to pragma 'optimize' [-Wpragmas]
bridges.cpp:2:88: warning: bad option '-fsse2' to pragma 'optimize' [-Wpragmas]
bridges.cpp:2:88: warning: bad option '-fsse3' to pragma 'optimize' [-Wpragmas]
bridges.cpp:2:88: warning: bad option '-fssse3' to pragma 'optimize' [-Wpragmas]
bridges.cpp:2:88: warning: bad option '-fsse4' to pragma 'optimize' [-Wpragmas]
bridges.cpp:2:88: warning: bad option '-fpopcnt' to pragma 'optimize' [-Wpragmas]
bridges.cpp:2:88: warning: bad option '-fabm' to pragma 'optimize' [-Wpragmas]
bridges.cpp:2:88: warning: bad option '-fmmx' to pragma 'optimize' [-Wpragmas]
bridges.cpp:2:88: warning: bad option '-ffma' to pragma 'optimize' [-Wpragmas]
bridges.cpp:2:88: warning: bad option '-ftune=native' to pragma 'optimize' [-Wpragmas]
bridges.cpp:20:45: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   20 |     dsu_data(int _a,int _sz1,int _b,int _sz2):a(_a),sz1(_sz1),b(_b),sz2(_sz2){}
      |                                             ^
bridges.cpp:20:45: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
bridges.cpp:20:45: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
bridges.cpp:20:45: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
bridges.cpp:20:45: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:20:45: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:20:45: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
bridges.cpp:20:45: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
bridges.cpp:20:45: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
bridges.cpp:20:45: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
bridges.cpp:20:45: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
bridges.cpp:20:45: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
bridges.cpp:25:20: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   25 |     void init(int n){
      |                    ^
bridges.cpp:25:20: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
bridges.cpp:25:20: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
bridges.cpp:25:20: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
bridges.cpp:25:20: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:25:20: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:25:20: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
bridges.cpp:25:20: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
bridges.cpp:25:20: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
bridges.cpp:25:20: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
bridges.cpp:25:20: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
bridges.cpp:25:20: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
bridges.cpp:31:19: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   31 |     int find(int x){
      |                   ^
bridges.cpp:31:19: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
bridges.cpp:31:19: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
bridges.cpp:31:19: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
bridges.cpp:31:19: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:31:19: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:31:19: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
bridges.cpp:31:19: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
bridges.cpp:31:19: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
bridges.cpp:31:19: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
bridges.cpp:31:19: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
bridges.cpp:31:19: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
bridges.cpp:35:27: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   35 |     void Merge(int a,int b){
      |                           ^
bridges.cpp:35:27: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
bridges.cpp:35:27: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
bridges.cpp:35:27: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
bridges.cpp:35:27: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:35:27: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:35:27: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
bridges.cpp:35:27: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
bridges.cpp:35:27: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
bridges.cpp:35:27: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
bridges.cpp:35:27: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
bridges.cpp:35:27: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
bridges.cpp:43:19: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   43 |     void rollback(){
      |                   ^
bridges.cpp:43:19: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
bridges.cpp:43:19: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
bridges.cpp:43:19: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
bridges.cpp:43:19: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:43:19: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:43:19: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
bridges.cpp:43:19: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
bridges.cpp:43:19: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
bridges.cpp:43:19: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
bridges.cpp:43:19: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
bridges.cpp:43:19: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
bridges.cpp:52:20: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   52 |     void undo(int t){
      |                    ^
bridges.cpp:52:20: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
bridges.cpp:52:20: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
bridges.cpp:52:20: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
bridges.cpp:52:20: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:52:20: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:52:20: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
bridges.cpp:52:20: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
bridges.cpp:52:20: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
bridges.cpp:52:20: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
bridges.cpp:52:20: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
bridges.cpp:52:20: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
bridges.cpp: In member function 'void dsu::undo(int)':
bridges.cpp:53:25: warning: comparison of integer expressions of different signedness: 'std::stack<dsu_data>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |         while (st.size()>t)
      |                ~~~~~~~~~^~
bridges.cpp: At global scope:
bridges.cpp:59:28: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   59 |     Query(int x,int y,int z):type(x),a(y),b(z){}
      |                            ^
bridges.cpp:59:28: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
bridges.cpp:59:28: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
bridges.cpp:59:28: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
bridges.cpp:59:28: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:59:28: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:59:28: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
bridges.cpp:59:28: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
bridges.cpp:59:28: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
bridges.cpp:59:28: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
bridges.cpp:59:28: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
bridges.cpp:59:28: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
bridges.cpp:63:33: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   63 |     bool operator<(const Edge a)const{
      |                                 ^~~~~
bridges.cpp:63:33: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
bridges.cpp:63:33: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
bridges.cpp:63:33: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
bridges.cpp:63:33: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:63:33: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:63:33: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
bridges.cpp:63:33: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
bridges.cpp:63:33: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
bridges.cpp:63:33: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
bridges.cpp:63:33: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
bridges.cpp:63:33: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
bridges.cpp:75:21: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   75 | bool cmp(pii a,pii b){
      |                     ^
bridges.cpp:75:21: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
bridges.cpp:75:21: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
bridges.cpp:75:21: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
bridges.cpp:75:21: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:75:21: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:75:21: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
bridges.cpp:75:21: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
bridges.cpp:75:21: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
bridges.cpp:75:21: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
bridges.cpp:75:21: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
bridges.cpp:75:21: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
bridges.cpp:79:12: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   79 | void solve(){
      |            ^
bridges.cpp:79:12: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
bridges.cpp:79:12: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
bridges.cpp:79:12: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
bridges.cpp:79:12: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:79:12: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:79:12: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
bridges.cpp:79:12: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
bridges.cpp:79:12: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
bridges.cpp:79:12: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
bridges.cpp:79:12: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
bridges.cpp:79:12: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
bridges.cpp:106:13: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
  106 | signed main(){
      |             ^
bridges.cpp:106:13: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
bridges.cpp:106:13: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
bridges.cpp:106:13: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
bridges.cpp:106:13: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:106:13: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
bridges.cpp:106:13: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
bridges.cpp:106:13: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
bridges.cpp:106:13: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
bridges.cpp:106:13: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
bridges.cpp:106:13: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
bridges.cpp:106:13: warning: bad option '-ftune=native' 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