Submission #282003

#	Time	Username	Problem	Language	Result	Execution time	Memory
282003		bigg	Valley (BOI19_valley)	C++14	36 / 100	23 ms	640 KiB

valley

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int MAXN = 1e3 + 10;
int n;
vector<pair<int, pair<int, ll> > >grafo[MAXN];
ll dist[MAXN];

void dfs(int x, int p, int ip){
	for(int i = 0; i < grafo[x].size(); i++){
		int viz = grafo[x][i].first, id = grafo[x][i].second.first;
		if(viz == p || id == ip) continue;
		dist[viz] = dist[x] + grafo[x][i].second.second;
		dfs(viz, x, ip);
	}
}
int s, e, q;
std::vector<int> shops;
int main(){
	scanf("%d %d %d %d", &n, &s, &q, &e);
	for(int i = 1; i < n; i++){
		int u, v;
		ll w;
		scanf("%d %d %lld", &u, &v, &w);
		grafo[u].push_back(make_pair(v, make_pair(i, w)));
		grafo[v].push_back(make_pair(u, make_pair(i, w)));

	}
	for(int i = 0; i < s; i++){
		int k;
		scanf("%d", &k);
		shops.push_back(k);

	}
	for(int i = 1; i <= q; i++){
		for(int j = 1; j <= n; j++) dist[j] = INF;
		int id, k;
		scanf("%d %d", &id, &k);
		dist[k] = 0;
		dfs(k, 0, id);
		if(dist[e] < INF){
			printf("escaped\n" );
			continue;
		}
		bool ok = 0;
		ll minx = INF;
		for(int j = 0; j < shops.size(); j++){
			if(dist[shops[j]] < INF){
				ok = 1;
				minx = min(dist[shops[j]], minx);
			}
		}
		if(!ok) printf("oo\n");
		else printf("%lld\n", minx );
	}

}

Compilation message (stderr)

valley.cpp: In function 'void dfs(int, int, int)':
valley.cpp:11:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for(int i = 0; i < grafo[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~
valley.cpp: In function 'int main()':
valley.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for(int j = 0; j < shops.size(); j++){
      |                  ~~^~~~~~~~~~~~~~
valley.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   21 |  scanf("%d %d %d %d", &n, &s, &q, &e);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |   scanf("%d %d %lld", &u, &v, &w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |   scanf("%d", &k);
      |   ~~~~~^~~~~~~~~~
valley.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |   scanf("%d %d", &id, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

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