#include <bits/stdc++.h>
using namespace std;
// Miscellanous
#define gc getchar_unlocked
#define ll long long
#define ull unsigned long long
#define si(x) scanf("%d",&x)
#define si2(x,y) scanf("%d %d",&x,&y)
#define sl(x) scanf("%lld",&x)
#define sl2(x,y) scanf("%lld %lld",&x,&y)
#define sstr(s) cin >> s
#define pi(x) printf("%d\n",x)
#define pi2(x,y) printf("%d %d\n",x,y)
#define pl(x) printf("%lld\n",x)
#define pl2(x,y) printf("%lld %lld\n",x,y)
#define ps(s) cout << s << endl
#define py printf("YES\n")
#define pn printf("NO\n")
#define pnl printf("\n")
#define pb push_back
#define ff first
#define ss second
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define sortv(v) sort(all(v))
#define revsort(v) sort(v.rbegin(),v.rend())
#define reverse(v) reverse(all(v))
#define alla(arr,sz) arr,arr+sz
#define sorta(arr,sz) sort(alla(arr,sz))
#define reversea(arr,sz) reverse(alla(arr,sz))
#define cta(x,v) count(alla(arr,sz),x)
#define ct(x,v) count(all(v),x)
#define cto(v) count_if(all(v),[] (int a) {return a%2 == 1;})
#define cte(v) count_if(all(v),[] (int a) {return a%2 == 0;})
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define clr(x) memset(x, 0, sizeof(x))
// Loops
#define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
#define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
#define forc(c,s,e) for (char (c)=(s);(c)<=(e);++(c))
#define forr(i,s,e) for (int (i)=(s);(i)>=(e);--(i))
#define foreach(val,cont) for (auto &(val) : (cont))
#define rep(i,n) loop(i,0,n)
#define repn(i,n) loope(i,1,n)
// Constants
#define PI 3.1415926535897932384626
#define sqr(x) ((x) * 1ll * (x))
const int mod = 1000000007;
// Containers
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<string,string> pss;
typedef map<int, int> mii;
// Input Output
#define takei(a) int a; si(a)
#define takei2(a,b) int a,b; si2(a,b)
#define takel(a) ll a; sl(a)
#define takel2(a,b) ll a,b; sl2(a,b)
#define takearri0(n,a) vi a(n); rep(i,n) si(a[i])
#define takearri1(n,a) vi a(n+1); a[0] = 0; repn(i,n) si(a[i])
#define takearrl0(n,a) vl a(n); rep(i,n) sl(a[i])
#define takearrl1(n,a) vl a(n+1); a[0] = 0ll; repn(i,n) sl(a[i])
// Debug
void _print(int t) {cerr << t;}
void _print(ll t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(unordered_set <T> v);
template <class T> void _print(unordered_multiset <T> v);
template <class T> void _print(set <T> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(unordered_map <T, V> v);
template <class T, class V> void _print(unordered_multimap <T, V> v);
template <class T, class V> void _print(map <T, V> v);
template <class T, class V> void _print(multimap <T, V> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(unordered_set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(unordered_multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(unordered_map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(unordered_multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
#ifndef ONLINE_JUDGE
#define deb(x) cerr << #x << " = "; _print(x); cerr << endl;
#else
#define deb(x)
#endif
inline string inttostr(ll a){
char x[100];
sprintf(x,"%lld",a); string s = x;
return s;
}
inline ll strtoint(string a){
char x[100]; ll res;
strcpy(x,a.c_str()); sscanf(x,"%lld",&res);
return res;
}
inline string getstr(void){
char x[1000005];
scanf("%s",x); string s = x;
return s;
}
inline string uppercase(string s){
int n = sz(s);
rep(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
return s;
}
inline string lowercase(string s){
int n = sz(s);
rep(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
return s;
}
// ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
// Link --> https://oj.uz/problem/view/BOI19_valley
#define MAXN 100005
#define LOG 17
int up[MAXN][LOG];
ll upf[MAXN][LOG];
int tin[MAXN], tout[MAXN];
vpii adj[MAXN];
ll d[MAXN], dp[MAXN], depth[MAXN];
vector<bool> is_shop(MAXN, 0);
int root,t;
void find_d(int v, int p, int wt)
{
if(v != root) d[v] = d[p] + wt, depth[v] = depth[p] + 1;
for(auto ed : adj[v]) if(ed.ff != p) find_d(ed.ff, v, ed.ss);
}
ll dfs(int v, int p)
{
ll ans = LONG_LONG_MAX;
for(auto ed : adj[v]) if(ed.ff != p) ans = min(ans, dfs(ed.ff,v));
if(is_shop[v]) ans = d[v];
if(ans != LONG_LONG_MAX) dp[v] = ans - 2*d[v];
else dp[v] = LONG_LONG_MAX;
return ans;
}
void dfs1(int v, int p)
{
tin[v] = t++;
up[v][0] = p;
repn(i,LOG-1) up[v][i] = up[up[v][i-1]][i-1];
upf[v][0] = dp[v];
repn(i,LOG-1) upf[v][i] = min(upf[v][i-1], upf[up[v][i-1]][i-1]);
for(auto ed : adj[v]) if(ed.ff != p) dfs1(ed.ff, v);
tout[v] = t++;
}
int kth_ancestor(int v, int k)
{
if(k > depth[v]) return -1;
for (int i = LOG-1; i >= 0; i--)
{
if((1<<i) <= k) v = up[v][i] , k -= (1<<i);
}
return v;
}
int lca(int a, int b)
{
if(depth[a] < depth[b]) swap(a,b);
// Moving a UP the tree so both a and b are on the SAME level
a = kth_ancestor(a, depth[a] - depth[b]);
if(a == b) return a; // If they are on the same node, lca found
// We move BOTH a and b UP by the SAME distance whenever we can
for (int i = LOG-1; i >= 0; i--)
{
if(up[a][i] != up[b][i]) a = up[a][i], b = up[b][i];
}
return up[a][0];
}
bool is_ancestor(int anc, int v)
{
return tin[anc] <= tin[v] and tout[anc] >= tout[v];
}
// Return value --> MINIMUM of wt of NODES along the path a--b
ll query(int a, int b)
{
int c = lca(a,b); // c --> LCA of a and b
ll ans = LONG_LONG_MAX; int k;
k = depth[a] - depth[c] + 1;
for (int i = LOG-1; i >= 0; i--)
{
if((1<<i) <= k) ans = min(ans, upf[a][i]), a = up[a][i] , k -= (1<<i);
}
k = depth[b] - depth[c] + 1;
for (int i = LOG-1; i >= 0; i--)
{
if((1<<i) <= k) ans = min(ans, upf[b][i]), b = up[b][i] , k -= (1<<i);
}
return ans;
}
int main()
{
takei2(n,m);
takei(q); si(root);
vvi edges(n);
repn(i,n-1)
{
takei2(u,v); takei(wt);
edges[i] = {u,v,wt};
adj[u].pb({v,wt});
adj[v].pb({u,wt});
}
while(m--) {takei(c); is_shop[c] = 1;}
// Constructing d array
d[root] = depth[root] = 0; find_d(root,root,0);
// Constructing DP array
dfs(root,root);
// Precomputation for BINARY LIFTING
t = 0; dfs1(root,root);
while(q--)
{
takei2(i,r);
int u = edges[i][0] , v = edges[i][1];
if(is_ancestor(u,v)) swap(u,v);
if(!is_ancestor(u,r)) cout << "escaped\n";
else
{
ll ans = query(r,u);
if(ans == LONG_LONG_MAX) cout << "oo\n";
else pl(ans + d[r]);
}
}
return 0;
}
// ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Compilation message
valley.cpp: In function 'std::string uppercase(std::string)':
valley.cpp:42:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
42 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
valley.cpp:47:18: note: in expansion of macro 'loop'
47 | #define rep(i,n) loop(i,0,n)
| ^~~~
valley.cpp:138:3: note: in expansion of macro 'rep'
138 | rep(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
| ^~~
valley.cpp: In function 'std::string lowercase(std::string)':
valley.cpp:42:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
42 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
valley.cpp:47:18: note: in expansion of macro 'loop'
47 | #define rep(i,n) loop(i,0,n)
| ^~~~
valley.cpp:144:3: note: in expansion of macro 'rep'
144 | rep(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
| ^~~
valley.cpp: In function 'void dfs1(int, int)':
valley.cpp:43:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
43 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
| ^
valley.cpp:48:19: note: in expansion of macro 'loope'
48 | #define repn(i,n) loope(i,1,n)
| ^~~~~
valley.cpp:188:3: note: in expansion of macro 'repn'
188 | repn(i,LOG-1) up[v][i] = up[up[v][i-1]][i-1];
| ^~~~
valley.cpp:43:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
43 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
| ^
valley.cpp:48:19: note: in expansion of macro 'loope'
48 | #define repn(i,n) loope(i,1,n)
| ^~~~~
valley.cpp:191:3: note: in expansion of macro 'repn'
191 | repn(i,LOG-1) upf[v][i] = min(upf[v][i-1], upf[up[v][i-1]][i-1]);
| ^~~~
valley.cpp: In function 'int main()':
valley.cpp:43:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
43 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
| ^
valley.cpp:48:19: note: in expansion of macro 'loope'
48 | #define repn(i,n) loope(i,1,n)
| ^~~~~
valley.cpp:258:3: note: in expansion of macro 'repn'
258 | repn(i,n-1)
| ^~~~
valley.cpp:9:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
9 | #define si2(x,y) scanf("%d %d",&x,&y)
| ~~~~~^~~~~~~~~~~~~~~
valley.cpp:69:30: note: in expansion of macro 'si2'
69 | #define takei2(a,b) int a,b; si2(a,b)
| ^~~
valley.cpp:254:3: note: in expansion of macro 'takei2'
254 | takei2(n,m);
| ^~~~~~
valley.cpp:8:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
8 | #define si(x) scanf("%d",&x)
| ~~~~~^~~~~~~~~
valley.cpp:68:25: note: in expansion of macro 'si'
68 | #define takei(a) int a; si(a)
| ^~
valley.cpp:255:3: note: in expansion of macro 'takei'
255 | takei(q); si(root);
| ^~~~~
valley.cpp:8:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
8 | #define si(x) scanf("%d",&x)
| ~~~~~^~~~~~~~~
valley.cpp:255:13: note: in expansion of macro 'si'
255 | takei(q); si(root);
| ^~
valley.cpp:9:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
9 | #define si2(x,y) scanf("%d %d",&x,&y)
| ~~~~~^~~~~~~~~~~~~~~
valley.cpp:69:30: note: in expansion of macro 'si2'
69 | #define takei2(a,b) int a,b; si2(a,b)
| ^~~
valley.cpp:260:5: note: in expansion of macro 'takei2'
260 | takei2(u,v); takei(wt);
| ^~~~~~
valley.cpp:8:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
8 | #define si(x) scanf("%d",&x)
| ~~~~~^~~~~~~~~
valley.cpp:68:25: note: in expansion of macro 'si'
68 | #define takei(a) int a; si(a)
| ^~
valley.cpp:260:18: note: in expansion of macro 'takei'
260 | takei2(u,v); takei(wt);
| ^~~~~
valley.cpp:8:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
8 | #define si(x) scanf("%d",&x)
| ~~~~~^~~~~~~~~
valley.cpp:68:25: note: in expansion of macro 'si'
68 | #define takei(a) int a; si(a)
| ^~
valley.cpp:265:15: note: in expansion of macro 'takei'
265 | while(m--) {takei(c); is_shop[c] = 1;}
| ^~~~~
valley.cpp:9:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
9 | #define si2(x,y) scanf("%d %d",&x,&y)
| ~~~~~^~~~~~~~~~~~~~~
valley.cpp:69:30: note: in expansion of macro 'si2'
69 | #define takei2(a,b) int a,b; si2(a,b)
| ^~~
valley.cpp:278:5: note: in expansion of macro 'takei2'
278 | takei2(i,r);
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
3 ms |
8796 KB |
Output is correct |
| 3 |
Correct |
3 ms |
8796 KB |
Output is correct |
| 4 |
Correct |
4 ms |
8540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
3 ms |
8796 KB |
Output is correct |
| 3 |
Correct |
3 ms |
8796 KB |
Output is correct |
| 4 |
Correct |
4 ms |
8540 KB |
Output is correct |
| 5 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 6 |
Correct |
3 ms |
8552 KB |
Output is correct |
| 7 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 8 |
Correct |
3 ms |
8948 KB |
Output is correct |
| 9 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 10 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 11 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 12 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 13 |
Correct |
2 ms |
8792 KB |
Output is correct |
| 14 |
Correct |
2 ms |
8796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
129 ms |
35924 KB |
Output is correct |
| 2 |
Correct |
159 ms |
39328 KB |
Output is correct |
| 3 |
Correct |
144 ms |
39232 KB |
Output is correct |
| 4 |
Correct |
157 ms |
41044 KB |
Output is correct |
| 5 |
Correct |
129 ms |
41044 KB |
Output is correct |
| 6 |
Correct |
153 ms |
42916 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
3 ms |
8796 KB |
Output is correct |
| 3 |
Correct |
3 ms |
8796 KB |
Output is correct |
| 4 |
Correct |
4 ms |
8540 KB |
Output is correct |
| 5 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 6 |
Correct |
3 ms |
8552 KB |
Output is correct |
| 7 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 8 |
Correct |
3 ms |
8948 KB |
Output is correct |
| 9 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 10 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 11 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 12 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 13 |
Correct |
2 ms |
8792 KB |
Output is correct |
| 14 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 15 |
Correct |
129 ms |
35924 KB |
Output is correct |
| 16 |
Correct |
159 ms |
39328 KB |
Output is correct |
| 17 |
Correct |
144 ms |
39232 KB |
Output is correct |
| 18 |
Correct |
157 ms |
41044 KB |
Output is correct |
| 19 |
Correct |
129 ms |
41044 KB |
Output is correct |
| 20 |
Correct |
153 ms |
42916 KB |
Output is correct |
| 21 |
Correct |
123 ms |
39228 KB |
Output is correct |
| 22 |
Correct |
137 ms |
38756 KB |
Output is correct |
| 23 |
Correct |
142 ms |
38572 KB |
Output is correct |
| 24 |
Correct |
145 ms |
40660 KB |
Output is correct |
| 25 |
Correct |
145 ms |
43600 KB |
Output is correct |
| 26 |
Correct |
125 ms |
39004 KB |
Output is correct |
| 27 |
Correct |
126 ms |
38740 KB |
Output is correct |
| 28 |
Correct |
135 ms |
38640 KB |
Output is correct |
| 29 |
Correct |
153 ms |
40012 KB |
Output is correct |
| 30 |
Correct |
145 ms |
41552 KB |
Output is correct |
| 31 |
Correct |
123 ms |
39280 KB |
Output is correct |
| 32 |
Correct |
144 ms |
38864 KB |
Output is correct |
| 33 |
Correct |
148 ms |
38956 KB |
Output is correct |
| 34 |
Correct |
151 ms |
40608 KB |
Output is correct |
| 35 |
Correct |
144 ms |
43348 KB |
Output is correct |
| 36 |
Correct |
141 ms |
40788 KB |
Output is correct |
