이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
vector <int> v[100005],inv[100005];
int n,m,q,i,fr[100005],val[100005],ok[100005],distfin[100005],teste;
pair <int,int > dist[100005][305];
int mar[100005];
vector <pair <int,int>> acum;
vector <int> salut;
bool compare (pair <int,int> a,pair <int,int> b)
{
return a.second>b.second;
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0);
#ifdef HOME
ifstream cin("date.in");
ofstream cout("date.out");
#endif // HOME
cin>>n>>m>>teste;
for (i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
if (x>y)
{
swap(x,y);
}
inv[y].push_back(x);
}
int bucket =300;
for (i=1;i<=n;i++)
{
int numar=0;
acum.clear();
salut.clear();
acum.push_back({i,0});
for (int j=0;j<inv[i].size();j++)
{
int nod = inv[i][j];
for (int k=1;k<=mar[nod];k++)
{
acum.push_back({dist[nod][k].first,dist[nod][k].second+1});
}
}
int lim = min((int)acum.size(),bucket);
sort (acum.begin(),acum.end(),compare);
for (int j=0;j<lim;j++)
{
if (fr[acum[j].second]==0)
{
fr[acum[j].second]=1;
mar[i]++;
dist[i][mar[i]]=acum[j];
salut.push_back(acum[j].second);
}
}
for (int j=0;j<salut.size();j++)
{
fr[salut[j]]=0;
}
}
for (i=1;i<=n;i++)
{
fr[i]=0;
}
for (;teste--;)
{
int nod,nr;
cin>>nod >> nr;
for (i=1;i<=nr;i++)
{
cin>>val[i];
fr[val[i]]=1;
}
if (nr>=bucket)
{
vector<int> dp(n, -1);
for (int i = 0; i <= nod; i ++){
if (fr[i]==0){
dp[i] = max(dp[i], 0);
}
for (int j = 0; j < (int)inv[i].size(); j ++){
if (dp[inv[i][j]] != -1) dp[i] = max(dp[i], dp[inv[i][j]] + 1);
}
}
cout << dp[nod] << '\n';
}
else
{
int solfin=-1;
for (int j=1;j<=mar[nod];j++)
{
int nod2 = dist[nod][j].first;
if (fr[nod2]==0)
{
solfin=max(solfin,dist[nod][j].second);
}
}
cout<<solfin<<'\n';
}
for (i=1;i<=nr;i++)
{
fr[val[i]]=0;
}
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
bitaro.cpp: In function 'int main()':
bitaro.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for (int j=0;j<inv[i].size();j++)
| ~^~~~~~~~~~~~~~
bitaro.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for (int j=0;j<salut.size();j++)
| ~^~~~~~~~~~~~~
bitaro.cpp:37:13: warning: unused variable 'numar' [-Wunused-variable]
37 | int numar=0;
| ^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |