oj.uz

Submission #1081083

# Submission time Handle Problem Language Result Execution time Memory
1081083 2024-08-29T18:08:30 Z Rawlat_vanak Cyberland (APIO23_cyberland) C++17
0 / 100
 572 ms 25800 KB 
#include <bits/stdc++.h>
using namespace std;
//#define long long long long
#define speedIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define f first
#define s second
#define pii pair<double,long long>
#define pb push_back

vector<vector<pair<long long, long long>>> graph;
vector<long long> parent,sz;

long long find(long long u){
	while(u!=parent[u]) u=parent[u];
	return parent[u];
}

void unite(long long a,long long b){
	a=find(a);b=find(b);
	if(a==b) return;
	if(sz[b]>sz[a]) swap(a,b);
	parent[b]=a;
	sz[a]+=sz[b];

}

double solve(int N,int M,int K,int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
	long long n=N,m=M,k=K,h=H;
	parent.resize(n);
	for(long long i=0;i<n;i++){
		parent[i]=i;
	}
	sz.resize(n,1);
	graph.resize(n);
	for(long long i=0;i<n;i++){
		graph[x[i]].pb({y[i],c[i]});
		graph[y[i]].pb({x[i],c[i]});
		unite(x[i],y[i]);
	}

	priority_queue<pii> q;
	vector<vector<double>> dist(n,vector<double>(k+1,1e15));
	vector<bool> visited(n,false);
	
	for(long long j=0;j<=k;j++){
		if(find(0)==find(h)){
			dist[0][j]=0;
			q.push({0,0});
		}
		visited[0]=false;
		for(long long i=1;i<n;i++){
			visited[i]=false;
			if(arr[i]==0 and find(i)==find(h)){
				dist[i][j]=0;
				q.push({0,i});
			}
		}
		while(!q.empty()){
				pii u=q.top();
				long long v=u.s;
				q.pop();
				if(visited[v]) continue;
				visited[v]=true;
				for(pii w: graph[v]){
					long long xxxx=w.f;
					if(arr[xxxx]==1){
						if(dist[w.f][j]>dist[v][j]+w.s){
							dist[w.f][j]=dist[v][j]+w.s;
							q.push({-dist[w.f][j],w.f});
						}
					}else if(arr[xxxx]==2){
						if(dist[w.f][j]>dist[v][j]+w.s){
							dist[w.f][j]=dist[v][j]+w.s;
							q.push({-dist[w.f][j],w.f});
						}
						if(j>=1){
							if(dist[xxxx][j]>(dist[v][j-1]+w.s)/2){
								dist[xxxx][j]=(dist[v][j-1]+w.s)/2;
								q.push({-dist[xxxx][j],xxxx});
							}
						}
					}
				}
		}
	}
	double ans=1e15;
	for(long long i=0;i<=k;i++){
		ans=min(ans,dist[h][i]);
	}

	for(long long i=0;i<n;i++){
		graph[i].clear();
		dist[i].clear();
		parent.clear();
		visited.clear();
		sz.clear();
	}
	if(ans==1e15){
		return -1;
	}else{
		return ans;
	}

}

Compilation message

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:29:16: warning: unused variable 'm' [-Wunused-variable]
   29 |  long long n=N,m=M,k=K,h=H;
      |                ^

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1372 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 896 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 572 ms 25800 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1372 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -