Submission #282039

#	Time	Username	Problem	Language	Result	Execution time	Memory
282039		bigg	Valley (BOI19_valley)	C++14	100 / 100	307 ms	44792 KiB

valley

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int MAXN = 1e5 + 10;
const int MAXL = 23;
int n;
vector<pair<int, int > >grafo[MAXN];
int tin[MAXN], tout[MAXN], altura[MAXN];
int sparse[MAXN][MAXL];
ll dist[MAXN], dpaux[MAXN], dp[MAXN][MAXL];
bool isshop[MAXN], hasshop[MAXN];
int T;
void dfs(int x, int p){
	//printf("oi\n");
	tin[x] = ++T;
	hasshop[x] = isshop[x];
	if(isshop[x])dpaux[x] = dist[x];
	else dpaux[x] = INF;

	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;
		altura[viz] = altura[x] + 1;
		dist[viz] = dist[x] + grafo[x][i].second;

		dfs(viz, x);
		dpaux[x] = min(dpaux[x], dpaux[viz]);
		hasshop[x] |= hasshop[viz];
	}
	//if(dpaux[x] < INF) dpaux[x] -= 2*dist[x];

	tout[x] =T;
}
void dfs2(int x, int p){
	//printf("%d %d\n",x, p );
	dp[x][0] = dpaux[x];
	for(int k = 1; k < MAXL; k++){
		sparse[x][k] = sparse[sparse[x][k-1]][k-1];
		dp[x][k] = min(dp[x][k-1], dp[sparse[x][k-1]][k-1]);
	}
	for(int i = 0; i < grafo[x].size(); i++){
		int viz = grafo[x][i].first;
		if(viz == p) continue;
		sparse[viz][0] = x;
		dfs2(viz, x);
	}
}
bool checkin(int id1, int id2){
	if(tin[id1] <= tin[id2] && tout[id1] >= tin[id2] ) return true;
	return false;
}
ll query(int x, int p){
	ll ans = INF;
	for(int k = MAXL  - 1; k >= 0; k--){
		if(checkin(p, sparse[x][k])){
			ans = min(ans, dp[x][k]);
			x = sparse[x][k];
		}
		
	}
	ans = min(ans, dpaux[p]);
	return ans;
}
int s, e, q;
//std::vector<int> shops;
pair<int, int> arestas[MAXN];

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, w));
		grafo[v].push_back(make_pair(u, w));
		arestas[i] = make_pair(u, v);

	}

	for(int i = 0; i < s; i++){
		int k;
		scanf("%d", &k);
		isshop[k] = 1;
	}
	dfs(e, 0);
	for(int i = 1; i <= n; i++){
		if(dpaux[i] < INF) dpaux[i] -= 2*dist[i];
	}
	dfs2(e, 0);
	for(int i = 1; i <= q; i++){
		//printf("kkk\n");
		int id, k;
		scanf("%d %d", &id, &k);
		int u = arestas[id].first, v = arestas[id].second;
		if(altura[u] < altura[v]) swap(u, v);
		if(checkin(u, k)){
			//if(isshop[k]) printf("0\n");
			if(hasshop[u])printf("%lld\n", dist[k] + query(k, u) );
			else printf("oo\n");
		}
		else printf("escaped\n");
	}

}

Compilation message (stderr)

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

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