Submission #290279

#TimeUsernameProblemLanguageResultExecution timeMemory
290279NaimSSBridges (APIO19_bridges)C++14
73 / 100
3077 ms11296 KiB
#include <bits/stdc++.h> #define ld long double #define endl "\n" #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define pb(x) push_back(x) #define mp(a,b) make_pair(a,b) #define ms(v,x) memset(v,x,sizeof(v)) #define all(v) v.begin(),v.end() #define ff first #define ss second #define rep(i, a, b) for(int i = a; i < (b); ++i) #define per(i, a, b) for(int i = b-1; i>=a ; i--) #define trav(a, x) for(auto& a : x) #define allin(a , x) for(auto a : x) #define Unique(v) sort(all(v));v.erase(unique(all(v)),v.end()); #define sz(v) (int)v.size() //#define int long long using namespace std; typedef vector<int> vi; #define y1 abacaba #define left sefude #define db(x) cerr << #x <<" == "<<x << endl; #define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl; #define db3(x,y,z) cerr << #x<<" == "<<x<<", "<<#y<<" == "<<y<<", "<<#z<<" == "<<z<<endl; typedef long long ll; typedef pair<int,int> pii; inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; } ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));} ll exp(ll a,ll b,ll m){ if(b==0LL) return 1LL; if(b==1LL) return mod(a,m); ll k = mod(exp(a,b/2,m),m); if(b&1LL){ return mod(a*mod(k*k,m),m); } else return mod(k*k,m); } struct DSU{ vi pai,ps; DSU(){} DSU(int n){ pai.resize(n+1); ps.resize(n+1); for(int i=1;i<=n;i++)pai[i]=i,ps[i]=1; } int f(int x){ return pai[x] = (pai[x]==x?x:f(pai[x])); } int getsz(int x){ return ps[f(x)]; } void join(int a,int b){ a=f(a),b=f(b); if(a==b)return; if(ps[a]>ps[b]){int c=a;a=b,b=c;} ps[b]+=ps[a]; pai[a]=b; } }; const int N = 50100,M = 100100; const int sq = 400; vi g[N]; // guarda os ids int a[M],b[M],c[M]; int res[M]; int vis[N]; int T=0; int t[M],s[M],w[M]; int m,n; vector<int> ar[N]; bool jf[M]; DSU dsu(0); int dfs(int v){ vis[v] = T; int r = dsu.getsz(v); for(int to : ar[v])if(vis[to]!=T){ r+=dfs(to); } return r; } bool used[M]; vi edge; // O(N*sq^2 + MlogM * M/sq + Q*sq + ) void go(vi qry){ vi Q,upd; for(int id : qry){ if(t[id] == 2)Q.pb(id); else{ upd.pb(id); used[s[id]] = 1; } } vi unused; for(int i=1;i<=m;i++){ // O(M) if(used[i]){ unused.pb(i); continue; } } sort(all(Q),[&](int a,int b){ return w[a] > w[b]; }); // sqrt * log(sqrt); dsu = DSU(n); // O(N * alpha) reverse(all(upd)); int curedge = 0; for(int id : Q){ while(curedge < sz(edge) and c[edge[curedge]]>=w[id]){ // O(M) // gogo int ed = edge[curedge]; if(used[ed]){ curedge++; continue; } dsu.join(a[ed],b[ed]); curedge++; } T++; for(int id2 : upd){ if(id2 > id || jf[s[id2]])continue; jf[s[id2]] = 1; if(w[id2] >= w[id]){ // add edge: int ed = s[id2]; ar[dsu.f(a[ed])].pb(dsu.f(b[ed])); ar[dsu.f(b[ed])].pb(dsu.f(a[ed])); } } for(int id2 : unused){ if(!jf[id2] and c[id2] >= w[id]){ ar[dsu.f(a[id2])].pb(dsu.f(b[id2])); ar[dsu.f(b[id2])].pb(dsu.f(a[id2])); jf[id2] = 1; } } res[id] = dfs(dsu.f(s[id])); // rool back for(int id2 : upd){ jf[s[id2]] = 0; int ed = s[id2]; ar[dsu.f(a[ed])].clear(); ar[dsu.f(b[ed])].clear(); } for(int id2 : unused){ jf[id2] = 0; ar[dsu.f(a[id2])].clear(); ar[dsu.f(b[id2])].clear(); } } for(int ed : unused){ used[ed] = 0; } // update the edges: for(int id : qry){ if(t[id] == 1){ c[s[id]] = w[id]; } } sort(all(edge),[&](int a,int b){ return c[a] > c[b]; }); } int32_t main(){ fastio; cin>>n>>m; for(int i=1;i<=m;i++){ cin >> a[i] >> b[i] >> c[i]; edge.pb(i); } sort(all(edge),[&](int a,int b){ return c[a] > c[b]; }); int q; cin >> q; vi qry; for(int i=0;i<q;i++){ cin >> t[i] >> s[i] >> w[i]; qry.pb(i); if(sz(qry) == sq){ go(qry); qry.clear(); } } go(qry); for(int i=0;i<q;i++){ if(t[i] == 2)cout << res[i] << endl; } // math -> gcd it all // Did u check N=1? Did you switch N,M? }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...