#include <bits/stdc++.h>
using namespace std;
void fast(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
const int N=1e5;
const double INF=1e16;
int n, m, k, h;
vector<pair<int,int>> v[N+1], ad; //adventure graph
vector<int> a;
bool f=false; //find cyberland
void dfs(int node, int p){
if(f) return;
for(auto [i, d]:v[node]){
if(i==p) continue;
int di=0;
if(a[i]!=0) di=d;
ad.push_back({di, a[i]});
if(i==h) f=true;
dfs(i, node);
}
if(f) return;
ad.pop_back();
}
priority_queue<tuple<double,int,int>, vector<tuple<double,int,int>>, greater<tuple<double,int,int>>> pq;
double solve(int nn, int mm, int kk, int hh, vector<int> x, vector<int> y, vector<int> c, vector<int> aa){
n=nn, m=mm, k=kk, h=hh, a=aa;
for(int i=0; i<m; i++){
v[x[i]].push_back({y[i], c[i]});
v[y[i]].push_back({x[i], c[i]});
}
// if(m==n-1){
// dfs(0, -1);
// priority_queue<int> pqq;
// double ans=0;
// for(auto [p, q]:ad){
// if(q==2) pqq.push(p);
// else ans+=p;
// }
// while(!pqq.empty()){
// int u=pqq.top(); pqq.pop();
// if(k) ans+=double(u)/2;
// else ans+=u;
// k--;
// }
// return ans;
// }
vector<vector<double>> dp(n+1, vector<double>(k+1, INF));
dp[0][0]=0;
pq.push({0, 0, 0}); //not yet disc
while(!pq.empty()){
auto[d, u, dis]=pq.top(); pq.pop();
for(auto [to, dist]:v[u]){
if(a[to]==0){
if(0<dp[to][dis]){
dp[to][dis]=0;
pq.push({0, to, dis});
}
}
else if(a[to]==1){
if(dp[u][dis]+dist<dp[to][dis]){
dp[to][dis]=dp[u][dis]+dist;
pq.push({dp[to][dis], to, dis});
}
}
else{
if(dp[u][dis]+dist<dp[to][dis]){
dp[to][dis]=dp[u][dis]+dist;
pq.push({dp[to][dis], to, dis});
}
if(dis<k && (dp[u][dis]+dist)/2<dp[to][dis]){
dp[to][dis]=(dp[u][dis]+dist)/2;
pq.push({dp[to][dis], to, dis});
}
}
}
}
double ans=INF;
for(int i=0; i<=k; i++) ans=min(ans, dp[h][i]);
return ans;
}
/*
int main(){
fast();
int n, m, k, h; cin>>n>>m>>k>>h;
vector<int> x(N+1), y(N+1), c(N+1), a(N+1);
for(int i=0; i<m; i++){
cin>>x[i]>>y[i]>>c[i];
}
for(int i=0; i<n; i++) cin>>a[i];
cout<<solve(n, m, k, h, x, y, c, a);
}
*/
/*
const int N=2e5;
int lv[N+1], bl[N+1][20];
bool cek[N+1], vis[N+1];
vector<int> v[N+1], c[N+1], b[N+1], ans;
void dfs(int node, int p){
bl[node][0]=p;
for(int i=1; i<20; i++) bl[node][i]=bl[bl[node][i-1]][i-1];
for(auto i:v[node]){
if(i==p) continue;
lv[i]=lv[node]+1;
dfs(i, node);
}
}
int lca(int x, int y){
if(lv[y]>lv[x]) swap(x, y);
int d=lv[x]-lv[y];
for(int i=19; i>=0; i--) if((1<<i)&d) x=bl[x][i];
if(x==y) return x;
for(int i=19; i>=0; i--){
if(bl[x][i]!=bl[y][i]){
x=bl[x][i];
y=bl[y][i];
}
}
return bl[x][0];
}
void off(int node, int p){
if(vis[node]) return;
vis[node]=true;
for(auto i:v[node]){
if(i==p) continue;
off(i, node);
}
for(auto i:c[node]) cek[i]=true;
for(auto i:b[node]) cek[i]=true;
}
void dfs2(int node, int p){
for(auto i:v[node]){
if(i==p) continue;
dfs2(i, node);
}
for(auto i:c[node]){
if(!cek[i]){
ans.push_back(node);
off(node, p);
}
}
}
int main(){
fast();
int n, m; cin>>n>>m;
for(int i=1; i<n; i++){
int x, y; cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1, 0);
for(int i=1; i<=m; i++){
int x, y; cin>>x>>y;
c[lca(x, y)].push_back(i);
b[x].push_back(i);
b[y].push_back(i);
}
dfs2(1, 0);
cout<<ans.size()<<'\n';
for(auto &i:ans) cout<<i<<' ';
}
*/
/*
int main(){
fast();
int n, m; cin>>n>>m;
vector<int> v[n+1];
bool s1=true, s2=true;
for(int i=1; i<n; i++){
int x, y; cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
if(x!=i || y!=i+1) s2=false;
}
int x[m+1], y[m+1];
for(int i=1; i<=m; i++){
cin>>x[i]>>y[i];
if(x[i]!=y[i]) s1=false;
}
if(s1){
set<int> t;
for(int i=1; i<=n; i++) t.insert(x[i]);
cout<<t.size();
return 0;
}
if(s2){
}
}
*/
/*
const int INF=1e9;
int main(){
fast();
int n; cin>>n;
int a[n+1], b[n+1], c[n+1];
for(int i=1; i<=n; i++) cin>>c[i];
for(int i=1; i<=n; i++) cin>>a[i];
for(int i=1; i<=n; i++) cin>>b[i];
int ki=0, ka=INF, ans=0;
while(ki<=ka){
int mid=(ki+ka)/2;
bool can=true;
int minxa=INF, minxb=INF, use;
for(int i=1; i<=n; i++){
long long temp=1ll*mid*min(a[i], b[i]);
if(temp>c[i]){
can=false;
break;
}
use=c[i]-temp;
if(a[i]<b[i]){
minxb=min(minxb, use/(b[i]-a[i]));
}
else if(a[i]>b[i]){
minxa=min(minxa, use/(a[i]-b[i]));
}
}
if(can && minxa+minxb>=mid){
ans=mid;
ki=mid+1;
}
else ka=mid-1;
}
cout<<ans;
}
*/
/*
const int INF=1e9;
int main(){
fast();
int n; cin>>n;
int a[n+1], b[n+1], c[n+1];
for(int i=1; i<=n; i++) cin>>c[i];
int minxa=INF, minxb=INF, resa=INF, resb=INF;
for(int i=1; i<=n; i++) cin>>a[i];
for(int i=1; i<=n; i++){
cin>>b[i];
minxa=min(minxa, c[i]/a[i]);
minxb=min(minxb, c[i]/b[i]);
}
for(int i=1; i<=n; i++){
int sisaa=c[i]-minxa*a[i], sisab=c[i]-minxb*b[i];
if(sisaa==0) resa=0;
else resa=min(resa, sisaa/b[i]);
if(sisab==0) resb=0;
else resb=min(resb, sisab/a[i]);
}
cout<<max(minxa+resa, minxb+resb);
}
*/
/*
const int INF=1e9;
int main(){
fast();
int n; cin>>n;
int a[n+1], b[n+1], c[n+1];
for(int i=1; i<=n; i++) cin>>c[i];
int m=INF, ans=0;
for(int i=1; i<=n; i++){
cin>>a[i];
m=min(m, c[i]/a[i]);
}
bool same=true;
for(int i=1; i<=n; i++) {cin>>b[i]; same&=(a[i]==b[i]);}
if(same){
cout<<m;
return 0;
}
for(int i=0; i<=m; i++){
int minx=INF;
for(int j=1; j<=n; j++){
int res=(c[j]-i*a[j]);
if(res==0){minx=0; continue;}
minx=min(minx, res/b[j]);
}
ans=max(ans, i+minx);
cout<<i<<' '<<minx<<'\n';
}
cout<<ans;
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1328 ms |
3480 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
5972 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
6100 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
23628 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
5956 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
5844 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
5572 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
674 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
