이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
struct wi{
vector<int> Q;
int odl=1e9;
}*w;
int ojc[200000];
int pocz[200000];
int kon[200000];
int ostd[200000];
int kraw[200000][2];
int zapp[200000][2];
int find_u(int x)
{
if(ojc[x]==x)
return x;
return ojc[x]=find_u(ojc[x]);
}
void union_f(int x,int y)
{
//cout<<"lacze "<<x<<" "<<y<<"\n";
ojc[find_u(x)]=find_u(y);
}
int32_t main()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
int n,m,x,y,z;
cin>>n>>m;
w=new wi[n+3];
for(int i=1;i<=m;i++)
{
cin>>x>>y>>z;
w[x].Q.push_back(y);
w[y].Q.push_back(x);
w[x].Q.push_back(z);
w[y].Q.push_back(z);
kraw[i][0]=x;
kraw[i][1]=y;
}
int mam;
cin>>mam;
priority_queue<pair<int,int> > kolejka;
for(int i=1;i<=mam;i++)
{
cin>>x;
kolejka.push({0,x});
}
while(!kolejka.empty())
{
auto para=kolejka.top();
kolejka.pop();
int x=para.second;
int ile=-para.first;
if(w[x].odl!=1e9)
continue;
w[x].odl=ile;
for(int i=0;i<w[x].Q.size();i+=2)
{
int pom=w[x].Q[i];
if(w[pom].odl!=1e9)
continue;
kolejka.push({-ile-w[x].Q[i+1],pom});
}
}
int zap;
cin>>zap;
for(int i=1;i<=zap;i++)
{
cin>>x>>y;
pocz[i]=0,kon[i]=1e9,ostd[i]=-1;
zapp[i][0]=x;
zapp[i][1]=y;
}
vector<pair<int,pair<int,int> > > krawedzie;
for(int i=1;i<=m;i++)
{
x=kraw[i][0];
y=kraw[i][1];
krawedzie.push_back({min(w[x].odl,w[y].odl),{x,y}});
//cout<<"wrzucam "<<x<<" "<<y<<": "<<w[x].odl<<" "<<w[y].odl<<"\n";
}
sort(krawedzie.begin(),krawedzie.end());
for(int a=0;a<=30;a++)
{
//cout<<a<<": ";
for(int i=1;i<=n;i++)
ojc[i]=i;
vector<pair<pair<int,int>,pair<int,int> > > wydarzenia;
for(int i=1;i<=zap;i++)
wydarzenia.push_back({{(pocz[i]+kon[i])/2,i},{zapp[i][0],zapp[i][1]}});
int gdzie=wydarzenia.size()-1;
sort(wydarzenia.begin(),wydarzenia.end());
while(gdzie>=0 && wydarzenia[gdzie].first.first>krawedzie.back().first)
{
int x=wydarzenia[gdzie].second.first;
int y=wydarzenia[gdzie].second.second;
int co=wydarzenia[gdzie].first.second;
if(find_u(x)!=find_u(y))
{
kon[co]=wydarzenia[gdzie].first.first;
//cout<<"essa "<<co<<" "<<wydarzenia[gdzie].first.first<<" "<<krawedzie.back().first<<"\n";
}
else{
//cout<<"dobrze "<<wydarzenia[gdzie].first.first<<" dla "<<x<<" "<<y<<"\n";
pocz[co]=wydarzenia[gdzie].first.first+1;
ostd[co]=wydarzenia[gdzie].first.first;
}
gdzie--;
}
for(int i=krawedzie.size()-1;i>=0;i--)
{
union_f(krawedzie[i].second.first,krawedzie[i].second.second);
if(i>0 && krawedzie[i].first==krawedzie[i-1].first)
continue;
while(gdzie>=0 && (i==0 || wydarzenia[gdzie].first.first>krawedzie[i-1].first))
{
int x=wydarzenia[gdzie].second.first;
int y=wydarzenia[gdzie].second.second;
int co=wydarzenia[gdzie].first.second;
if(find_u(x)!=find_u(y))
kon[co]=wydarzenia[gdzie].first.first;
else{
//cout<<"dobrze "<<wydarzenia[gdzie].first.first<<" dla "<<x<<" "<<y<<"\n";
pocz[co]=wydarzenia[gdzie].first.first+1;
ostd[co]=wydarzenia[gdzie].first.first;
}
gdzie--;
}
}
}
for(int i=1;i<=zap;i++)
cout<<ostd[i]<<"\n";
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
plan.cpp: In function 'int32_t main()':
plan.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int i=0;i<w[x].Q.size();i+=2)
| ~^~~~~~~~~~~~~~
# | 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... |