Submission #675038

#	Time	Username	Problem	Language	Result	Execution time	Memory
675038		MohammadAghil	Bridges (APIO19_bridges)	C++17	73 / 100	3022 ms	19504 KiB

bridges

      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
 using namespace std;
  typedef long long ll;
   typedef pair<int, int> pp;
     #define per(i,r,l) for(int i = (r); i >= (l); i--)
       #define rep(i,l,r) for(int i = (l); i < (r); i++)
          #define all(x) begin(x), end(x)
             #define sz(x) (int)(x).size()
                 #define pb push_back
                     #define ss second
                          #define ff first
                                  void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     #ifndef ONLINE_JUDGE
          #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
     #else
          #define er(args ...) 0
     #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353, maxn = 1e5 + 5, sq = 500, lg = 22, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll,md);return k*k%md*(b&1ll?a:1)%md;}

int par[maxn], cnt[maxn];
int get(int x){
     return par[x] == -1? x: par[x] = get(par[x]);
}
void unite(int u, int v){
     u = get(u), v = get(v);
     if(u - v){
          cnt[u] += cnt[v];
          par[v] = u;
     }
}
int n, m;
vector<int> adj[maxn];
bool vis[maxn];
int dfs(int r){
     vis[r] = true;
     int res = cnt[r];
     for(int c: adj[r]) if(!vis[c]) res += dfs(c); 
     return res;
}
int u[maxn], v[maxn], cr[maxn];
vector<pp> edge;
bool is_edge[maxn], use[maxn];

vector<int> slv(vector<pair<int, pp>> query){
     fill(par, par + n, -1), fill(cnt, cnt + n, 1), fill(is_edge, is_edge + m, false);
     vector<pair<pp, int>> srt;
     rep(i,0,sz(query)){
          auto[t, p] = query[i];
          auto[x, w] = p;
          if(t == 1){
               is_edge[x] = true;
          }else{
               srt.pb({{w, x}, i});
          }
     }
     int t = 0;
     reverse(all(query));
     rep(i,0,m) if(is_edge[i]) query.pb({1, {i, cr[i]}}), t++;
     reverse(all(query));
     for(auto&c: srt) c.ss += t;
     sort(all(srt));
     vector<int> tmp(sz(query), -1);
     int ptr = m-1;
     per(i,sz(srt)-1,0){
          auto[w, x] = srt[i].ff;
          while(ptr + 1 && edge[ptr].ff >= w){
               if(!is_edge[edge[ptr].ss]){
                    unite(u[edge[ptr].ss], v[edge[ptr].ss]);
               }
               ptr--;
          }
          int id = srt[i].ss;
          // er(i, w, x, id);
          vector<int> seen;
          per(j,id-1,0){
               auto[t, p] = query[j];
               auto[xx, ww] = p;
               if(t == 1){
                    seen.pb(xx);
                    if(ww >= w && !use[xx]){
                         adj[get(u[xx])].pb(get(v[xx]));
                         adj[get(v[xx])].pb(get(u[xx]));
                    }
                    use[xx] = true;
               }
          }
          tmp[id] = dfs(get(x));
          vis[get(x)] = false;
          for(int c: seen) use[c] = false, adj[get(u[c])].clear(), adj[get(v[c])].clear(), vis[get(u[c])] = vis[get(v[c])] = false;
     }
     vector<pp> nw, nw2;
     for(auto[w, id]: edge){
          if(!is_edge[id]) nw.pb({w, id});
     }
     per(i,sz(query)-1,0){
          auto[t, p] = query[i];
          auto[x, w] = p;
          if(t == 1){
               if(!use[x]){
                    nw2.pb({w, x});
                    cr[x] = w;
               }
               use[x] = true;
          }
     }
     for(auto[w, x]: nw2) use[x] = false;
     sort(all(nw2));
     edge.clear();
     merge(all(nw), all(nw2), back_inserter(edge));
     vector<int> ans;
     for(int c: tmp) if(c + 1) ans.pb(c);
     return ans; 
}

int main(){ IOS();
     cin >> n >> m;
     rep(i,0,m){
          int w; cin >> u[i] >> v[i] >> w; u[i]--, v[i]--;
          edge.pb({w, i});
          cr[i] = w;
     }
     sort(all(edge));
     int q; cin >> q;
     vector<pair<int, pp>> query;
     rep(i,1,q+1){
          int t, x, w; cin >> t >> x >> w; x--;
          query.pb({t, {x, w}});
          if(i%sq == 0){
               for(int c: slv(query)) cout << c << '\n';
               query.clear();
          }
     }
     if(sz(query)){
          for(int c: slv(query)) cout << c << '\n';
          query.clear();
     }
     return 0-0;
}

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