제출 #432957

#제출 시각아이디문제언어결과실행 시간메모리
432957TLP39다리 (APIO19_bridges)C++14
16 / 100
871 ms10688 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<ll,ll> pll; int n,m,q; int seg[200012]={}; int a[50003]; vector<pair<int,int>> adj[50003]; bool mark[1003]; int bfs(int v,int w) { for(int i=0;i<1003;i++) mark[i]=false; int ans=1; queue<int> qq; qq.push(v); mark[v]=true; int fr; while(!qq.empty()) { fr=qq.front(); qq.pop(); for(int i=0;i<adj[fr].size();i++) { if(a[adj[fr][i].second]>w) continue; if(mark[adj[fr][i].first]) continue; mark[adj[fr][i].first]=true; ans++; qq.push(adj[fr][i].first); } } return ans; } void solve_1() { int t,u,v; while(q--) { scanf("%d %d %d",&t,&u,&v); if(t==1) { a[u]=v; } else { printf("%d\n",bfs(u,v)); } } } void build(int v,int st,int ed) { if(st==ed) { seg[v]=a[st]; return; } int mid=(st+ed)>>1; build(v<<1,st,mid); build(1+(v<<1),mid+1,ed); seg[v]=min(seg[v<<1],seg[1+(v<<1)]); } void upd(int v,int l,int r,int pos,int val) { if(l==r) { seg[v]=val; return; } int mid=(l+r)>>1; if(mid>=pos) upd(v<<1,l,mid,pos,val); else upd(1+(v<<1),mid+1,r,pos,val); seg[v]=min(seg[v<<1],seg[1+(v<<1)]); } int que(int v,int l,int r,int st,int ed) { if(st>ed) return 1000000001; if(l==st && r==ed) return seg[v]; int mid=(l+r)>>1; return min(que(v<<1,l,mid,st,min(mid,ed)),que(1+(v<<1),mid+1,r,max(mid+1,st),ed)); } int getlow(int x,int w) { if(x==1) return 1; int hi=x,low=1,av; while(hi>low) { av=(hi+low)>>1; if(que(1,1,m,av,x-1)>=w) hi=av; else low=av+1; } return hi; } int gethi(int x,int w) { if(x==n) return n; int low=x,hi=n,av; while(hi>low) { av=(hi+low+1)>>1; if(que(1,1,m,x,av-1)>=w) low=av; else hi=av-1; } return hi; } int main() { scanf("%d %d",&n,&m); int t1,t2; int t,u,v; for(int i=1;i<=m;i++) { scanf("%d %d %d",&t1,&t2,&a[i]); adj[t1].push_back({t2,i}); adj[t2].push_back({t1,i}); } if(n==1) { scanf("%d",&q); while(q--) { scanf("%d %d %d",&t,&u,&v); if(t==2) printf("1\n"); } return 0; } build(1,1,m); scanf("%d",&q); if(n<=1000 && m<=1000 && q<=10000) { solve_1(); return 0; } while(q--) { scanf("%d %d %d",&t,&u,&v); if(t==1) { upd(1,1,m,u,v); } else { printf("%d\n",gethi(u,v)-getlow(u,v)+1); } } }

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

bridges.cpp: In function 'int bfs(int, int)':
bridges.cpp:24: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]
   24 |         for(int i=0;i<adj[fr].size();i++)
      |                     ~^~~~~~~~~~~~~~~
bridges.cpp: In function 'void solve_1()':
bridges.cpp:41:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |             scanf("%d %d %d",&t,&u,&v);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         scanf("%d %d",&n,&m);
      |         ~~~~~^~~~~~~~~~~~~~~
bridges.cpp:121:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |             scanf("%d %d %d",&t1,&t2,&a[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:127:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |             scanf("%d",&q);
      |             ~~~~~^~~~~~~~~
bridges.cpp:130:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |                 scanf("%d %d %d",&t,&u,&v);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~
bridges.cpp:136:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         scanf("%d",&q);
      |         ~~~~~^~~~~~~~~
bridges.cpp:144:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |             scanf("%d %d %d",&t,&u,&v);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
#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...