Submission #898908

#	Time	Username	Problem	Language	Result	Execution time	Memory
898908		vjudge1	Magic Tree (CEOI19_magictree)	C++17	0 / 100	720 ms	1048576 KiB

magictree

//In the name of GOD***---...---***---...---***---...

/*/=======================================

Diversity in counsel, unity in command
__
Success always calls for greater generosity - though
most people, lost in the darkness of their own egos,
treat it as an occasion for greater greed.
Collecting boot is not an end itself, but only a means for
building an empire. Riches would be of little use to us now
except as a means of winning new friends.
__*By Cyrus the great*__

=======================================/*/
#include<bits/stdc++.h>
using namespace std;
////========== Defines ==============////
#define IOS ios_base::sync_with_stdio(0);\
	cin.tie(0);\
	cout.tie(0);
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define fixed(a) fixed<<setprecision(a)
////=============== Typedefs ==============////
typedef long long int lli;
typedef pair<lli,lli> pii;
////=============== CONSTANT ===============////
const lli mx = (1e3+100), inf = (1<<30);
////============== Global types ============////
lli n, s, q, e;
vector<pii> adj[mx];
lli dis[mx], st[mx];
pii ed[mx];
lli mini =inf;
lli POS, ban1, ban2;
bool check;
////========== User Define Functions ==========////
void dfs(lli p, lli v, lli wi){
	dis[v] = dis[p] + wi;
	if(v == e) mini = -1;
	if(v == POS) check =1;
	if(st[v] == 1) mini = min(mini, dis[v]);
//	cout << "we are in " << v << ' ' << dis[v] << '\n';
	for(auto u : adj[v]){
		if(u.F == p) continue;
		if(u.F == ban1 && v == ban2) continue;
		if(v == ban1 && u.F == ban2) continue;
		dfs(v, u.F, u.S);
	}
}
void solve(lli pos){
	POS = pos;
	if(n == s){
		dfs(0, e, 0);
		if(check) cout << "escaped\n";
		else cout << 0 << '\n';
	}
	else{
		dfs(0, POS, 0);
		if(mini == inf) cout << "oo\n";
		else{
			if(mini == -1) cout << "escaped\n";
			else cout << mini << '\n';
		}
	}
	cout << endl;
}
////================= Notes =================////
/*
15 4 1000 15
1 2 1
1 3 1
2 4 1
3 5 1
3 8 1
5 6 1
2 7 1
7 9 1
9 10 1
8 11 1
11 15 1
8 12 1
12 13 1
12 14 1
4
8
13
10
*/
////============ End of Templates ============////
int main() {
	IOS
	cin >> n >> s >> q >> e;
	for(lli i =1; i < n; i++){
		lli x, y, w;
		cin >> x >> y >> w;
		adj[x].pb(mp(y, w));
		adj[y].pb(mp(x, w));
		ed[i] = mp(x, y);
	}
	for(lli i =0; i < s; i++){
		lli x;
		cin >> x;
		st[x] =1;
	}
	while(q--){
		lli ban, pOs;
		cin >> ban >> pOs;
		ban1 = ed[ban].F;
		ban2 = ed[ban].S;
		mini =inf;
		check =0;
		memset(dis, 0, sizeof dis);
		solve(pOs);
	}
//;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
	return 0;
	
}
//Hewwo OwO

• Subtask 1: 0 / 6
• Subtask 2: 0 / 3
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17