oj.uz

Submission #979859

# Submission time Handle Problem Language Result Execution time Memory
979859 2024-05-11T14:01:50 Z SmuggingSpun Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 2 ms 4440 KB 
#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
template<class T>void minimize(T& a, T b){
	if(a > b){
		a = b;
	}
}
const int lim = 1e5 + 5;
int travel_plan(int n, int m, int R[][2], int L[], int k, int P[]){
	queue<int>q;
	vector<vector<ll>>dp(n, vector<ll>(2, INF));
	vector<int>deg(n, 0);
	vector<vector<int>>e(n);
	for(int i = 0; i < m; i++){
		deg[R[i][0]]++;
		deg[R[i][1]]++;
		e[R[i][0]].emplace_back(i);
		e[R[i][1]].emplace_back(i);
	}
	for(int i = 0; i < k; i++){
		dp[P[i]][0] = dp[P[i]][1] = deg[P[i]] = 0;
		q.push(P[i]);
	}
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(int i = 0; i < e[u].size(); i++){
			int v = R[e[u][i]][0] ^ R[e[u][i]][1] ^ u, w = L[e[u][i]];
			if(deg[v] > 0){
				if(dp[u][1] + w < dp[v][0]){
					dp[v][1] = dp[v][0];
					dp[v][0] = dp[u][1] + w;
				}
				else{
					minimize(dp[v][1], dp[u][1] + w);
				}
				if(--deg[v] == 0){
					q.push(v);
				}
			}
		}
	}
	return dp[0][1];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for(int i = 0; i < e[u].size(); i++){
      |                  ~~^~~~~~~~~~~~~

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -