#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int N=1e5+50;
const ll inf=1e18;
vector<pair<int,ll> >E[N];
map<pair<int,int>,bool>mapa;
map<pair<int,int>,ll>grana;
int deg[N],dp[N];
bool nesto[N],was[N],trenutno[N];
int travel_plan(int n, int m, int R[][2], int L[], int K, int P[])
{
for(int i=0;i<m;i++){
E[R[i][0]].pb({R[i][1],L[i]}),E[R[i][1]].pb({R[i][0],L[i]});
deg[R[i][0]]++,deg[R[i][1]]++;
grana[{R[i][0],R[i][1]}]=grana[{R[i][1],R[i][0]}]=L[i];
}
for(int i=0;i<K;i++) nesto[P[i]]=true,dp[P[i]]=0;
set<int>pored;
for(int i=0;i<n;i++){
if(nesto[i]){
trenutno[i]=true;
for(auto j:E[i]) if(!nesto[j.fi]) pored.insert(j.fi);
}
}
//for(auto i=pored.begin();i!=pored.end();i++) printf("%i ",*i);
//printf("\n");
dp[0]=-1;
int CT=n+100;
while(dp[0]==-1 || CT--){
int U=-1,mn=1e9;
for(auto i=pored.begin();i!=pored.end();i=next(i)){
vector<pair<int,int> >temp;
int u=*i;
for(auto j:E[u]){
if(trenutno[j.fi]) temp.pb({j.se+dp[j.fi],j.fi});
}
if(temp.size()>=2){
//sort(temp.begin(),temp.end());
int ind=0;
for(int i=0;i<temp.size();i++){
if(temp[ind].fi>temp[i].fi) ind=i;
}
int idx=0,vr2=1e9;
for(int i=0;i<temp.size();i++) if(vr2>temp[i].fi && i!=ind) idx=i,vr2=temp[i].fi;
//dp[u]=temp[1].fi;
if(mn>vr2){
U=u;
mn=vr2;
}
/*dp[u]=temp[1].fi;
for(auto j:temp){
deg[j.se]--;
deg[u]--;
}
was[*i]=true;
pored.erase(*i);
for(auto j:E[u]){
if(deg[j.fi]>=2) pored.insert(j.fi);
}
break;*/
}
}
//printf("%i %i\n",U,mn);
vector<pair<int,int> >temp;
int u=U;
for(auto j:E[u]){
if(trenutno[j.fi]) temp.pb({j.se+dp[j.fi],j.fi});
}
if(temp.size()>=2){
//sort(temp.begin(),temp.end());
int ind=0;
for(int i=0;i<temp.size();i++){
if(temp[ind].fi>temp[i].fi) ind=i;
}
int idx=0,vr2=1e9;
for(int i=0;i<temp.size();i++) if(vr2>temp[i].fi && i!=ind) idx=i,vr2=temp[i].fi;
dp[u]=vr2;//dp[u]=temp[1].fi;
for(auto j:temp){
deg[j.se]--;
if(deg[j.se]==0) trenutno[j.se]=false,was[j.se]=true;
deg[u]--;
//printf("%i: %i\n%i: %i\n",j.se,deg[j.se],u,deg[u]);
}
//was[u]=true;
trenutno[u]=true;
pored.erase(u);
for(auto j:E[u]){
if(!was[j.fi]) pored.insert(j.fi);
}
}
//printf("%i\n",pored.size());
//for(auto i=pored.begin();i!=pored.end();i++) printf("%i ",*i);
//printf("\n");
//for(int i=0;i<n;i++) if(trenutno[i]) printf("%i ",i);
//printf("\n");
}
return dp[0];
/*int U=0;int res=0;
while(!nesto[U]){
//printf("%i\n",U);
ll dist[n+10];int parent[n+10];
memset(parent,-1,sizeof(parent));
for(int i=0;i<n;i++) dist[i]=inf;
dist[U]=0;
priority_queue<pair<ll,int> >pq;
pq.push({0,U});
while(!pq.empty()){
int u=pq.top().se;ll w=-pq.top().fi;
pq.pop();
if(w>dist[u]) continue;
for(auto i:E[u]){
if(mapa[{i.fi,u}]) continue;
if(dist[i.fi]>dist[u]+i.se){
dist[i.fi]=dist[u]+i.se;
parent[i.fi]=u;
pq.push({-dist[i.fi],i.fi});
}
}
}
//for(int i=0;i<n;i++) printf("%i: %i %i\n",i,dist[i],parent[i]);
//printf("\n");
int mn=0;
for(int i=0;i<K;i++) if(dist[P[i]]<dist[P[mn]]) mn=i;
int tmp=mn;mn=P[mn];
//printf("%i %i\n",tmp,mn);
while(parent[mn]!=U) mn=parent[mn];
mapa[{U,mn}]=mapa[{mn,U}]=true;
mn=0;if(tmp==0) mn=K-1;
for(int i=0;i<K;i++) if(dist[P[i]]<dist[P[mn]] && i!=tmp) mn=i;
mn=P[mn];
while(parent[mn]!=U) mn=parent[mn];
mapa[{U,mn}]=mapa[{mn,U}]=true;
res+=grana[{U,mn}];
U=mn;
//printf("%i\n",mn);
}
return res;*/
}
Compilation message
crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:45: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]
45 | for(int i=0;i<temp.size();i++){
| ~^~~~~~~~~~~~
crocodile.cpp:49: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]
49 | for(int i=0;i<temp.size();i++) if(vr2>temp[i].fi && i!=ind) idx=i,vr2=temp[i].fi;
| ~^~~~~~~~~~~~
crocodile.cpp:48:9: warning: variable 'idx' set but not used [-Wunused-but-set-variable]
48 | int idx=0,vr2=1e9;
| ^~~
crocodile.cpp:77:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i=0;i<temp.size();i++){
| ~^~~~~~~~~~~~
crocodile.cpp:81:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for(int i=0;i<temp.size();i++) if(vr2>temp[i].fi && i!=ind) idx=i,vr2=temp[i].fi;
| ~^~~~~~~~~~~~
crocodile.cpp:80:8: warning: variable 'idx' set but not used [-Wunused-but-set-variable]
80 | int idx=0,vr2=1e9;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 4 |
Execution timed out |
2004 ms |
7000 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 4 |
Execution timed out |
2004 ms |
7000 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 4 |
Execution timed out |
2004 ms |
7000 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
