oj.uz

Submission #847650

# Submission time Handle Problem Language Result Execution time Memory
847650 2023-09-10T06:04:19 Z KN200711 Cyberland (APIO23_cyberland) C++17
49 / 100
 92 ms 28244 KB 
#include "cyberland.h"
# include <bits/stdc++.h>
# define fi first
# define se second
using namespace std;

bool vis[100001];
vector< pair<int, int> > edge[100001];
int h1;

void dfs(int a) {
	vis[a] = 1;
	if(a == h1) return;
	for(auto p : edge[a]) {
		if(!vis[p.fi]) dfs(p.fi);
	}
}

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
	K = min(K, 70);
	h1 = H;
	for(int i=0;i<N;i++) {
		vis[i] = 0;
		edge[i].clear();
	}
	for(int i=0;i<x.size();i++) {
		edge[x[i]].push_back(make_pair(y[i], c[i]));
		edge[y[i]].push_back(make_pair(x[i], c[i]));
	}
	dfs(0);
	
	vector< vector<double> > dp;
	dp.resize(K + 1);
	for(int i=0;i<=K;i++) {
		dp[i].resize(N);
		for(int c=0;c<N;c++) dp[i][c] = -1;
	}
	priority_queue< pair<double, pair<int, int> > > PQ;
	for(int d=0;d<N;d++) {
		if(d == 0 || (arr[d] == 0 && vis[d])) PQ.push(make_pair(0, make_pair(0, d)));
	}
	
	while(!PQ.empty()) {
		double a = PQ.top().fi;
		int nm = PQ.top().se.fi, pos = PQ.top().se.se;
		PQ.pop();
		
		if(nm > K) continue;
		if(dp[nm][pos] != -1) continue;
		dp[nm][pos] = -a;
	//	cout<<nm<<" "<<pos<<" "<<a<<endl;
		if(pos == H) break;
		
		for(auto p : edge[pos]) {
			if(arr[p.fi] == 0) continue;
			else if(arr[p.fi] == 1 && dp[nm][p.fi] == -1) PQ.push(make_pair(a - ((double) p.se), make_pair(nm, p.fi)));
			else if(arr[p.fi] == 2) {
				if(nm + 1 <= K && dp[nm+1][pos] == -1)PQ.push(make_pair((a - (double) p.se) / ((double) 2), make_pair(nm + 1, p.fi)));
				if(dp[nm][pos] == -1) PQ.push(make_pair((a - (double) p.se), make_pair(nm + 1, p.fi)));
			} 
		}
	}
	double ans = 1e18;
	for(int v=0;v<=K;v++) {
		if(dp[v][H] != -1) ans = min(ans, dp[v][H]);
	}
	if(ans == 1e18) ans = -1;
	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:26:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int i=0;i<x.size();i++) {
      |              ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2904 KB Correct.
2 Correct 24 ms 3160 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3160 KB Correct.
2 Correct 20 ms 3164 KB Correct.
3 Correct 18 ms 3160 KB Correct.
4 Correct 20 ms 3188 KB Correct.
5 Correct 26 ms 3120 KB Correct.
6 Correct 18 ms 5952 KB Correct.
7 Correct 23 ms 5636 KB Correct.
8 Correct 13 ms 9048 KB Correct.
9 Correct 22 ms 2904 KB Correct.
10 Correct 20 ms 2904 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3180 KB Correct.
2 Correct 25 ms 4240 KB Correct.
3 Correct 20 ms 4148 KB Correct.
4 Correct 23 ms 3672 KB Correct.
5 Correct 24 ms 3672 KB Correct.
6 Correct 5 ms 5464 KB Correct.

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 21716 KB Correct.
2 Incorrect 40 ms 4212 KB Wrong Answer.
3 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3204 KB Correct.
2 Correct 19 ms 3212 KB Correct.
3 Correct 19 ms 3232 KB Correct.
4 Correct 19 ms 5904 KB Correct.
5 Correct 19 ms 2904 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3216 KB Correct.
2 Correct 18 ms 4144 KB Correct.
3 Correct 45 ms 28244 KB Correct.
4 Correct 14 ms 5688 KB Correct.
5 Correct 21 ms 3672 KB Correct.
6 Correct 20 ms 4152 KB Correct.

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

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