Submission #840954

#	Time	Username	Problem	Language	Result	Execution time	Memory
840954		GoldLight	Cyberland (APIO23_cyberland)	C++17	0 / 100	1328 ms	2097152 KiB

cyberland

#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;
}*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3