Submission #131944

#	Time	Username	Problem	Language	Result	Execution time	Memory
131944		E869120	Valley (BOI19_valley)	C++14	36 / 100	3016 ms	14200 KiB

valley

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

int N, S, Q, E;
long long A[100009], B[100009], W[100009], dist[100009];
bool used[100009];

vector<pair<int, long long>> X[100009];

void dfs(int pos, long long dep) {
	if (dist[pos] != (1LL << 60)) return;
	dist[pos] = dep;
	for (int i = 0; i < X[pos].size(); i++) {
		dfs(X[pos][i].first, dep + X[pos][i].second);
	}
}

void solve(int I, int R) {
	for (int i = 1; i <= N; i++) { X[i].clear(); dist[i] = (1LL << 60); }
	for (int i = 1; i <= N - 1; i++) {
		if (i == I) continue;
		X[A[i]].push_back(make_pair(B[i], W[i]));
		X[B[i]].push_back(make_pair(A[i], W[i]));
	}
	dfs(R, 0);

	if (dist[E] != (1LL << 60)) {
		printf("escaped\n");
		return;
	}

	long long minx = (1LL << 60);
	for (int i = 1; i <= N; i++) {
		if (used[i] == true) minx = min(minx, dist[i]);
	}
	if (minx == (1LL << 60)) {
		printf("oo\n");
	}
	else {
		printf("%lld\n", minx);
	}
}

int main() {
	scanf("%d%d%d%d", &N, &S, &Q, &E);
	for (int i = 1; i <= N - 1; i++) {
		scanf("%lld%lld%lld", &A[i], &B[i], &W[i]);
	}
	for (int i = 1; i <= S; i++) {
		int t; scanf("%d", &t);
		used[t] = true;
	}
	for (int i = 1; i <= Q; i++) {
		int I, R; scanf("%d%d", &I, &R);
		solve(I, R);
	}
	return 0;
}

Compilation message (stderr)

valley.cpp:5:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
valley.cpp: In function 'void dfs(int, long long int)':
valley.cpp:16:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
valley.cpp: In function 'int main()':
valley.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &N, &S, &Q, &E);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &A[i], &B[i], &W[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:53:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int t; scanf("%d", &t);
          ~~~~~^~~~~~~~~~
valley.cpp:57:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int I, R; scanf("%d%d", &I, &R);
             ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 0 / 23
• Subtask 4: 0 / 41