이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |