Submission #1264118

#TimeUsernameProblemLanguageResultExecution timeMemory
1264118sasdeBridges (APIO19_bridges)C++17
100 / 100
1763 ms62304 KiB
#include<bits/stdc++.h> using namespace std; bool M1; #define PI 3.14159265358979323846 #define sz(a) (int)a.size() #define all(x) x.begin(),x.end() #define ii pair<int,int> #define iii pair<int,ii> #define iv pair<ii,ii> #define se second #define fi first #define ffi fi.fi #define sfi se.fi #define sse se.se #define fse fi.se #define lt(i, c, d) for(int i = c; i <= d; ++i) #define fl(i, c, d) for(int i = d; i >= c; --i) #define pb push_back #define emb emplace_back #define emf emplace_front #define em emplace #define look_memory cerr<<abs(&M2-&M1)/1024.0/1024<<'\n' #define look_time cerr << "TIME : " << clock() * 0.001 << "s" <<'\n' const int N=1e6+5,lg=30,mod=1e9+7,block=600; mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); int Rand(int u,int v){ return u+rd()%(v-u+1); } int dx[]={1,0,-1,0,1,1,-1,-1}; int dy[]={0,-1,0,1,1,-1,1,-1}; int node,query,edge,ans[N]; struct DSUrollback { struct State { int u, v, rku, rkv, timer,szu,szv; }; int n; vector<int> par, rk,siz; vector<State> history; DSUrollback() : n(0) {} DSUrollback(int _n) : n(_n), par(_n + 5), rk(_n + 5, 0), siz(n+5,1){ history.clear(); for (int i = 1; i <= n; ++i) par[i] = i; } void build(int _n) { *this = DSUrollback(_n); } int acs(int u) { while (par[u] != u) u = par[u]; return u; } bool join(int u, int v, int timer) { u = acs(u); v = acs(v); if (u == v) return false; if (rk[u] < rk[v]) std::swap(u, v); history.push_back({u, v, rk[u], rk[v], timer,siz[u],siz[v]}); siz[u]+=siz[v]; par[v] = u; if (rk[u] == rk[v]) rk[u]++; return true; } void rollback(int timer) { while (!history.empty() && history.back().timer >= timer) { State s = history.back(); history.pop_back(); par[s.u] = s.u; par[s.v] = s.v; rk[s.u] = s.rku; rk[s.v] = s.rkv; siz[s.u]=s.szu; siz[s.v]=s.szv; } } }; struct pt{ int u,v,w; }b[N]; struct pt1{ int t,x,y; }truyvan[N]; vector<int>nen,capnhat[N]; vector<int>req[N]; int last[N],truoc[N]; bool M2; void solve(){ cin >> node >> edge; for(int i=1;i<=edge;++i){ cin >> b[i].u >> b[i].v >> b[i].w; nen.emb(b[i].w); } int query; cin >> query; for(int i=1;i<=query;++i){ int t,x,y; cin >> t >> x >> y; truyvan[i]={t,x,y}; nen.emb(y); } sort(all(nen)); nen.erase(unique(all(nen)),nen.end()); for(int i=1;i<=edge;++i){ b[i].w=lower_bound(all(nen),b[i].w)-nen.begin()+1; } for(int i=1;i<=query;++i){ truyvan[i].y=lower_bound(all(nen),truyvan[i].y)-nen.begin()+1; if(truyvan[i].t==2){ truoc[i]=last[truyvan[i].x]; last[truyvan[i].x]=i; } } int n=sz(nen); for(int _=1;_<=query;_+=block){ int L=_; int R=min(query,_+block-1); vector<int>t1; vector<int>vis(edge+5,0),k1(edge+5,0); for(int i=L;i<=R;++i){ auto [t,x,y]=truyvan[i]; if(t==2){ capnhat[y].emb(i); } else{ vis[x]=true; t1.emb(i); } } for(int i=1;i<=edge;++i){ if(!vis[i]) req[b[i].w].emb(i); } DSUrollback dsu(node); int j=0; for(int i=n;i>=1;--i){ for(auto x:req[i]){ if(!vis[x]) dsu.join(b[x].u,b[x].v,-1); } for(auto x:capnhat[i]){ // cout <<i<<" "<<x<<'\n'; for(int j:t1){ if(j>x)break; k1[truyvan[j].x]=j; // if(x==3)cout <<j<<" "; } for(int j:t1){ if(truyvan[k1[truyvan[j].x]].y){ auto [t,u,v]=truyvan[k1[truyvan[j].x]]; // cout <<b[u].u<<" "<<b[u].v<<" "<<b[u].w<<" "<<i<<'\n'; if(v>=i) dsu.join(b[u].u,b[u].v,1); } else{ auto [t,u,v]=truyvan[j]; if(b[u].w>=i){ dsu.join(b[u].u,b[u].v,1); } } } ans[x]=dsu.siz[dsu.acs(truyvan[x].x)]; dsu.rollback(0); for(int j:t1){ if(j>x)break; k1[truyvan[j].x]=0; } } capnhat[i].clear(); req[i].clear(); } for(auto i:t1){ auto [t,x,y]=truyvan[i]; b[x].w=y; } } for(int i=1;i<=query;++i)if(truyvan[i].t==2)cout << ans[i]<<'\n'; } main() { srand(time(0)); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define task "aws" if(fopen(task".inp","r")){ freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } int t=1; // cin >> t; while(t--){ solve(); } look_memory; look_time; }

Compilation message (stderr)

bridges.cpp:189:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  189 | main()
      | ^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:197:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  197 |       freopen(task".inp","r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:198:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  198 |       freopen(task".out","w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...