이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define X first
#define Y second
int n,m,t,u_i,v_i,num,ban[100005],root=sqrt(100000),dp[100005];
int hsh[100005],party,hsh2[100005],ans;
int bug,bug2;
vector<int> from[100005];
vector<pair<int,int> > best[100005];
vector<pair<int,int> > merge(vector<pair<int,int> > v1,vector<pair<int,int> > v2)
{
/*if(bug==6&&bug2==5)
{
printf("v1\n");
for(int i=0;i<v1.size();i++)
{
printf("%d %d\n",v1[i].X,v1[i].Y);
}
printf("\n");
printf("v2\n");
for(int i=0;i<v2.size();i++)
{
printf("%d %d\n",v2[i],v2[i].Y);
}
printf("\n");
}*/
// printf("v1\n");
// for(int i=0;i<v1.size();i++)
// {
// printf("%d %d\n",v1[i].X,v1[i].Y);
// }
// printf("\n");
// printf("v2\n");
// for(int i=0;i<v2.size();i++)
// {
// printf("%d %d\n",v2[i],v2[i].Y);
// }
// printf("\n");
vector<pair<int,int> > v;
int it1=0,it2=0,it=0;
while(1)
{
if(v.size()==root)break;
if(it1==v1.size()&&it2==v2.size())break;
if(it1==v1.size())
{
if(hsh2[v2[it2].Y]==0)
{
hsh2[v2[it2].Y]=1;
v.pb({v2[it2].X+1,v2[it2].Y});
}
++it2;
}else if(it2==v2.size())
{
if(hsh2[v1[it1].Y]==0)
{
hsh2[v1[it1].Y]=1;
v.pb(v1[it1]);
}
++it1;
}else
{
if(v1[it1].X>v2[it2].X+1)
{
if(hsh2[v1[it1].Y]==0)
{
hsh2[v1[it1].Y]=1;
v.pb(v1[it1]);
}
++it1;
}else
{
if(hsh2[v2[it2].Y]==0)
{
hsh2[v2[it2].Y]=1;
v.pb({v2[it2].X+1,v2[it2].Y});
}
++it2;
}
}
++it;
}
for(int i=0;i<v1.size();i++)hsh2[v1[i].Y]=0;
for(int i=0;i<v2.size();i++)hsh2[v2[i].Y]=0;
/*if(bug==6&&bug2==5)
{
printf("vvv\n");
for(int i=0;i<v.size();i++)
{
printf("%d %d\n",v[i].X,v[i].Y);
}
}*/
/*printf("vvv\n");
for(int i=0;i<v.size();i++)
{
printf("%d %d\n",v[i].X,v[i].Y);
}*/
return v;
}
int main()
{
ios_base::sync_with_stdio(0),cin.tie(0);
//root=-1;
cin >> n >> m >> t;
for(int i=1;i<=m;i++)
{
cin >> u_i >> v_i;
from[v_i].pb(u_i);
}
for(int i=1;i<=n;i++)
{
//printf("iiiiiiiiiiii=%d\n",i);
best[i].pb({0,i});
for(auto node:from[i])
{
//printf("node=%d\n",node);
bug=i;
bug2=node;
best[i]=merge(best[i],best[node]);
/*if(i==6)
{
printf("node=%d\n",node);
for(int j=0;j<best[i].size();j++)
{
printf("%d %d\n",best[i][j].X,best[i][j].Y);
}
}*/
}
}
/*for(int i=1;i<=n;i++)
{
printf("i=%d\n",i);
for(int j=0;j<best[i].size();j++)
{
printf("%d %d\n",best[i][j].X,best[i][j].Y);
}
}*/
while(t--)
{
cin >> party >> num;
for(int i=1;i<=num;i++)
{
cin >> ban[i];
hsh[ban[i]]=1;
}
/*for(int i=1;i<=n;i++)
{
printf("%d ",hsh[i]);
}
printf("\n");*/
if(num>root)
{
for(int i=1;i<=n;i++)
{
dp[i]=-1e9;
if(hsh[i]==0)dp[i]=0;
for(auto node:from[i])
{
dp[i]=max(dp[i],dp[node]+1);
}
}
if(dp[party]<0)
{
printf("-1\n");
}else
{
printf("%d\n",dp[party]);
}
}else
{
ans=-1e9;
for(int i=0;i<best[party].size();i++)
{
if(hsh[best[party][i].Y]==0)
{
ans=max(ans,best[party][i].X);
}
}
/*for(int i=0;i<best[party].size();i++)
{
printf("%d %d\n",best[party][i].X,best[party][i].Y);
}*/
if(ans==-1e9)
{
printf("-1\n");
}else
{
printf("%d\n",ans);
}
}
for(int i=1;i<=num;i++)
{
hsh[ban[i]]=0;
}
}
}
컴파일 시 표준 에러 (stderr) 메시지
bitaro.cpp: In function 'std::vector<std::pair<int, int> > merge(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
bitaro.cpp:44:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
44 | if(v.size()==root)break;
| ~~~~~~~~^~~~~~
bitaro.cpp:45:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | if(it1==v1.size()&&it2==v2.size())break;
| ~~~^~~~~~~~~~~
bitaro.cpp:45:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | if(it1==v1.size()&&it2==v2.size())break;
| ~~~^~~~~~~~~~~
bitaro.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | if(it1==v1.size())
| ~~~^~~~~~~~~~~
bitaro.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | }else if(it2==v2.size())
| ~~~^~~~~~~~~~~
bitaro.cpp:84:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int i=0;i<v1.size();i++)hsh2[v1[i].Y]=0;
| ~^~~~~~~~~~
bitaro.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int i=0;i<v2.size();i++)hsh2[v2[i].Y]=0;
| ~^~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:173:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
173 | for(int i=0;i<best[party].size();i++)
| ~^~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |