제출 #340969

#제출 시각아이디문제언어결과실행 시간메모리
340969saleh다리 (APIO19_bridges)C++17
73 / 100
3030 ms7012 KiB
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> typedef int ll; typedef long double ld; #define pb push_back #define pii pair < int , int > #define F first #define S second #define endl '\n' //#define int long long #define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define kill(x) return cout<<x<<'\n', 0; using namespace std; const int N=5e4+2,sq=1000; struct IO_Tp{ bool is_digit(const char ch){ return '0' <= ch && ch <= '9'; } IO_Tp& operator>>(int& res){ res = 0; static char ch; while (ch = getchar(), !is_digit(ch)); do (res *= 10) += ch & 15; while (ch = getchar(), is_digit(ch)); return *this; } } IO; vector <pair <int,pii > > yy,yal; bitset<N*2> vis,vis2; ll nxt[N*2],pre[N*2]; ll par[N],sz[N]; ll getpar(ll v){ if (par[v]==v) return v; return par[v]=getpar(par[v]); } inline void mrg(ll v,ll u){ ll u1=getpar(u),v1=getpar(v); if (u1==v1) return ; if (sz[u1]>sz[v1])swap(u1,v1); par[u1]=v1; sz[v1]+=sz[u1]; } ll pp[N],zz[N]; ll gg(ll v){ if (pp[v]==v) return v; return pp[v]=gg(pp[v]); } inline void merg(ll v,ll u){ ll v1=gg(v),u1=gg(u); if (v1==u1) return ; if (zz[u1]>zz[v1]) swap(v1,u1); pp[u1]=v1; zz[v1]+=zz[u1]; } ll ans[N*2]; vector <pair <int,pii> > q; int main(){ sync; ll n,m; IO >> n >> m; for (int i=1;i<=m;i++){ ll u,v,w; IO >> u >> v >> w; yy.pb({w,{u,v}}); } ll q1; IO >> q1; while(q1--){ ll u,v,w; IO >> u >> v >> w; u--; q.pb({u,{v,w}}); } pre[0]=-1; nxt[q.size()-1]=5e6; for (int j=1;j<q.size();j++){ if (!q[j-1].F) pre[j]=j-1; else pre[j]=pre[j-1]; } for (int j=(ll)q.size()-2;j>-1;j--){ if (!q[j+1].F) nxt[j]=j+1; else nxt[j]=nxt[j+1]; } for (int i=0;i<q.size();i+=sq){ vector <pii> g; for (int j=i;j<min(i+sq,(int)q.size());j++){ if (!q[j].F) vis[q[j].S.F-1]=1; else{ g.pb({q[j].S.S,j}); } } memset(par,0,sizeof par); memset(sz,0,sizeof sz); for (int j=1;j<=n;j++){ sz[j]=1; par[j]=j; } yal.clear(); for (int j=0;j<yy.size();j++){ if (!vis[j]) yal.pb(yy[j]); } sort(yal.begin(),yal.end()); sort(g.begin(),g.end()); reverse(g.begin(),g.end()); ll cnt=0; for (int j=yal.size()-1;j>-1;j--){ while(cnt<g.size() && g[cnt].F>yal[j].F){ for (int k=i;k<min(i+sq,(ll)q.size());k++){ if (!q[k].F){ vis2[q[k].S.F-1]=0; ll v=yy[q[k].S.F-1].S.F,u=yy[q[k].S.F-1].S.S; pp[v]=getpar(v); pp[u]=getpar(u); zz[pp[v]]=sz[pp[v]]; zz[pp[u]]=sz[pp[u]]; pp[pp[v]]=pp[v]; pp[pp[u]]=pp[u]; } else{ ll v=q[k].S.F; pp[v]=getpar(v); zz[pp[v]]=sz[pp[v]]; pp[pp[v]]=pp[v]; } } ll id=g[cnt].S; for (int k=id;k>=i;k--){ if (q[k].F){ // cout << k << " " << pre[k] << endl; k=pre[k]+1; continue; } ll v=yy[q[k].S.F-1].S.F,u=yy[q[k].S.F-1].S.S; if (vis2[q[k].S.F-1]){ k=pre[k]+1; continue; } vis2[q[k].S.F-1]=1; if (q[k].S.S>=g[cnt].F){ merg(u,v); } k=pre[k]+1; } for (int k=id+1;k<min(i+sq,(ll)q.size());k++){ if (q[k].F){ k=nxt[k]-1; continue; } ll v=yy[q[k].S.F-1].S.F,u=yy[q[k].S.F-1].S.S; if (vis2[q[k].S.F-1]){ k=nxt[k]-1; continue; } vis2[q[k].S.F-1]=1; if (yy[q[k].S.F-1].F>=g[cnt].F){ merg(u,v); } k=nxt[k]-1; } ans[id]=zz[gg(q[id].S.F)]; cnt++; } mrg(yal[j].S.F,yal[j].S.S); } while(cnt<g.size()){ for (int k=i;k<min(i+sq,(ll)q.size());k++){ if (!q[k].F){ vis2[q[k].S.F-1]=0; ll v=yy[q[k].S.F-1].S.F,u=yy[q[k].S.F-1].S.S; pp[v]=getpar(v); pp[u]=getpar(u); zz[pp[v]]=sz[pp[v]]; zz[pp[u]]=sz[pp[u]]; pp[pp[u]]=pp[u]; pp[pp[v]]=pp[v]; } else{ ll v=q[k].S.F; pp[v]=getpar(v); zz[pp[v]]=sz[pp[v]]; pp[pp[v]]=pp[v]; } } ll id=g[cnt].S; for (int k=id;k>=i;k--){ if (q[k].F){ k=pre[k]+1; continue; } ll v=yy[q[k].S.F-1].S.F,u=yy[q[k].S.F-1].S.S; if (vis2[q[k].S.F-1]){ k=pre[k]+1; continue; } vis2[q[k].S.F-1]=1; if (q[k].S.S>=g[cnt].F){ merg(u,v); } k=pre[k]+1; } for (int k=id+1;k<min(i+sq,(ll)q.size());k++){ if (q[k].F) { k=nxt[k]-1; continue; } ll v=yy[q[k].S.F-1].S.F,u=yy[q[k].S.F-1].S.S; if (vis2[q[k].S.F-1]){ k=nxt[k]-1; continue; } vis2[q[k].S.F-1]=1; if (yy[q[k].S.F-1].F>=g[cnt].F){ merg(u,v); } k=nxt[k]-1; } ans[id]=zz[gg(q[id].S.F)]; cnt++; } for (int j=i;j<(min(i+sq,(ll)q.size()));j++){ if (!q[j].F){ yy[q[j].S.F-1].F=q[j].S.S; vis[q[j].S.F-1]=0; } } } string mas; for (int i=0;i<q.size();i++) if (q[i].F) { mas = to_string(ans[i]) + "\n"; char sam[11 + 2]{}; for (int i = 0; i < mas.size(); i++) sam[i] = mas[i]; cout << sam; } }

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

bridges.cpp: In function 'int main()':
bridges.cpp:78:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for (int j=1;j<q.size();j++){
      |                  ~^~~~~~~~~
bridges.cpp:86:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i=0;i<q.size();i+=sq){
      |                  ~^~~~~~~~~
bridges.cpp:101:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for (int j=0;j<yy.size();j++){
      |                      ~^~~~~~~~~~
bridges.cpp:110:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |             while(cnt<g.size() && g[cnt].F>yal[j].F){
      |                   ~~~^~~~~~~~~
bridges.cpp:168:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |         while(cnt<g.size()){
      |               ~~~^~~~~~~~~
bridges.cpp:232:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  232 |     for (int i=0;i<q.size();i++) if (q[i].F) {
      |                  ~^~~~~~~~~
bridges.cpp:235:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  235 |      for (int i = 0; i < mas.size(); i++) sam[i] = mas[i];
      |                      ~~^~~~~~~~~~~~
#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...