Submission #979859

#	Time	Username	Problem	Language	Result	Execution time	Memory
979859		SmuggingSpun	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	2 ms	4440 KiB

crocodile

#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 (stderr)

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
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11