제출 #491833

#제출 시각아이디문제언어결과실행 시간메모리
491833nikolapesic2802다리 (APIO19_bridges)C++14
59 / 100
3095 ms460284 KiB
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags #pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX #pragma GCC target("avx2") //Enable AVX #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/rope> #define ll long long #define pb push_back #define sz(x) (int)(x).size() #define mp make_pair #define f first #define s second #define all(x) x.begin(), x.end() #define D(x) cerr << #x << " is " << (x) << "\n"; using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key() template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; } template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;} template<class T> ostream& operator<<(ostream& os, const deque<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;} template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;} template<class T> ostream& operator<<(ostream& os, const set<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;} template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;} template<class T> ostream& operator<<(ostream& os, const multiset<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;} template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;} const int N=1e5+500,L=220,M=N/L; int u[N],v[N],w[N],last[N],qu[N],qw[N],ans[N]; vector<int> pojedinacno[N]; vector<pair<int,int> > arr[M]; int n,m,q,tr; void add(int l,int r,int in,int w){ //printf("%i-%i %i: %i %i %i\n",l,r,in,u[in],v[in],w); int le=l/L,ri=r/L; if(le==ri){ for(int i=l;i<=r;i++) if(qw[i]<=w) pojedinacno[i].pb(in); return; } if(l==le*L) le--; else for(int i=l;i<(le+1)*L;i++) if(qw[i]<=w) pojedinacno[i].pb(in); if(r==(ri+1)*L-1){ for(int i=le+1;i<=ri;i++) arr[i].pb({w,in}); } else{ for(int i=le+1;i<ri;i++) arr[i].pb({w,in}); for(int i=ri*L;i<=r;i++) if(qw[i]<=w) pojedinacno[i].pb(in); } } struct DSU{ vector<int> p,siz,in,undo; DSU(){p.resize(N);siz.resize(N,1);in.resize(N);iota(all(p),0);} void reset(){ for(auto d:undo) p[d]=d,in[d]=0,siz[d]=1; undo.clear(); } int find(int tr){return tr==p[tr]?tr:p[tr]=find(p[tr]);} void merge(int a,int b){ a=find(a); b=find(b); if(!in[a]) in[a]=1,undo.pb(a); if(a==b) return; if(!in[b]) in[b]=1,undo.pb(b); if(siz[a]<siz[b]){ siz[b]+=siz[a]; p[a]=b; } else{ siz[a]+=siz[b]; p[b]=a; } } }; void solve(){ DSU global,moj; for(int i=0;i<M;i++){ global.reset(); vector<pair<pair<int,int>,int> > query; for(int j=i*L;j<(i+1)*L&&~qu[j];j++) query.pb({{qw[j],qu[j]},j}); //cout << arr[i] << query << endl; sort(all(query)); reverse(all(query)); int ind=0; //printf("%i:-----------------------------------\n",i); for(auto p:query){ //printf("Racunam %i %i\n",p.f.f,p.f.s); while(ind<arr[i].size()&&arr[i][ind].f>=p.f.f) global.merge(u[arr[i][ind].s],v[arr[i][ind].s]),ind++; moj.reset(); for(auto d:pojedinacno[p.s]){ int uu=global.find(u[d]),vv=global.find(v[d]); //printf("Moj %i %i %i %i\n",uu,vv,moj.siz[uu],moj.siz[vv]); if(moj.siz[uu]<global.siz[uu]) moj.siz[uu]=global.siz[uu]; if(moj.siz[vv]<global.siz[vv]) moj.siz[vv]=global.siz[vv]; //printf("Moj %i %i %i %i\n",uu,vv,moj.siz[uu],moj.siz[vv]); moj.merge(uu,vv); } ans[p.s]=max(moj.siz[moj.find(global.find(p.f.s))],global.siz[moj.find(global.find(p.f.s))]); } for(int j=i*L;j<(i+1)*L&&~qu[j];j++) printf("%i\n",ans[j]); } } int main() { for(int i=0;i<N;i++) qu[i]=-1; //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); //n=50000; //m=100000; //int d=1e9; scanf("%i %i",&n,&m); for(int i=0;i<m;i++){ //u[i]=rng()%n;v[i]=rng()%n;w[i]=rng()%d; scanf("%i %i %i",&u[i],&v[i],&w[i]),u[i]--,v[i]--; } //q=100000; scanf("%i",&q); vector<tuple<int,int,int,int> > ad; for(int i=0;i<q;i++){ int t,a,b; //t=rng()%2+1; //a=rng()%n; //b=rng()%d; scanf("%i %i %i",&t,&a,&b); a--; if(t==2){ qu[tr]=a; qw[tr++]=b; }else{ if(last[a]!=tr) ad.pb(make_tuple(w[a],tr-1,a,last[a])); last[a]=tr; w[a]=b; } } for(int i=0;i<m;i++) if(last[i]!=tr) ad.pb(make_tuple(w[i],tr-1,i,last[i])); sort(all(ad)); reverse(all(ad)); for(auto p:ad){ int a,b,c,d; tie(d,b,c,a)=p; add(a,b,c,d); } solve(); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp:2: warning: ignoring '#pragma GCC option' [-Wunknown-pragmas]
    2 | #pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
      | 
bridges.cpp: In function 'void solve()':
bridges.cpp:109:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |             while(ind<arr[i].size()&&arr[i][ind].f>=p.f.f)
      |                   ~~~^~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:130:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  130 |     for(int i=0;i<N;i++)
      |     ^~~
bridges.cpp:137:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  137 |  scanf("%i %i",&n,&m);
      |  ^~~~~
bridges.cpp:137:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |  scanf("%i %i",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~
bridges.cpp:140:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |         scanf("%i %i %i",&u[i],&v[i],&w[i]),u[i]--,v[i]--;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:143:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |     scanf("%i",&q);
      |     ~~~~~^~~~~~~~~
bridges.cpp:150:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |         scanf("%i %i %i",&t,&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
#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...