/*
ID: awesome35
LANG: C++14
TASK: twofive
*/
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
#define ednl '\n'
#define test int t;cin>>t;while(t--)
#define pq priority_queue
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const int inf = 1000000007;//998244353
const ld pi = 3.1415926535;
ll maximum(ll x, ll y)
{
if (x > y)
return x;
return y;
}
ll minimum(ll x, ll y)
{
if (x < y)
return x;
return y;
}
void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
F0R(i, a.size()) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, a.size()) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
/*
void dijkstra(int i)
{//Preconditions for this to work: 1. no negative edges. 2. dist and parents are both initialized with size N and full of INT_MAX and 0 respectively while dist[i]=0 and parent[i]=-1
priority_queue<pii>todo;
vi finalized;
finalized.rsz(N + 1, 0);//make sure that the size of adjacency is N+1
todo.push(mp(0, i));
while (!todo.empty())
{//.s is indexs while .f is weight
pii temp = todo.top();
int indexs = temp.second;
todo.pop();
if (finalized[indexs])continue;
finalized[indexs] = 1;
trav(x, adjacency[indexs])
{
if (finalized[x.first])
continue;
if (dist[x.f] > x.s + dist[indexs])
{
dist[x.first] = x.second + dist[indexs];
parents[x.f] = indexs;
todo.push(mp(-dist[x.first], x.f));
}
}
}
}
void build_primes()
{
primes.reserve(50000);
vi visited;
visited.rsz(200000, 0);
FOR(i, 2, 200000)
{
if (visited[i] == 0)
{
primes.pb(i);
a = i;
while (a < 200000)
{
visited[a] = 1;
a += i;
}
}
}
}
//Prim's Algorithm
// need vector<vpi>adjacency
ll prim()
{
ll a = 0;
vi visited;
visited.rsz(n, 0);
visited[0] = 1;
pq<pii>todo;
trav(x, adjacency[0])
todo.push({ -x.s,x.f });
F0R(i, n - 1)
{
pii temp = todo.top();
todo.pop();
int indexs = temp.s;
if (visited[indexs])cont;
a -= temp.f;
visited[indexs] = 1;
trav(x, adjacency[indexs])
if (visited[x.f] == 0)
{
todo.push({ -x.s,x.f });
}
}
return a;
}
vector<vector<ll>> matrix_mult(vector<vector<ll>>& a, vector<vector<ll>>& b)
{
int n = a.size();
vector<vector<ll>> answer;
answer.resize(n);
for (int i = 0; i < n; i++) answer[i].resize(n, 0);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++) // calculate answer[i][j]
{
for (int k = 0; k < n; k++)
answer[i][j] = (answer[i][j] + a[i][k] * b[k][j]) % inf;
}
}
return answer;
}
vector<vector<ll>> matrix_exp(vector<vector<ll>>& a, ll n)
{
vector<vector<ll>> result;
result.resize(a.size());
for (int i = 0; i < a.size(); i++)
{
result[i].resize(a[0].size(), 0);
result[i][i] = 1;
}
while (n != 0)
{
if (n & 1)
result = matrix_mult(result, a);
a = matrix_mult(a, a);
n = n >> 1;
}
return result;
}
// Union-Find
int find(int a) // return the root for node a
{
if (a == links[a])
return a;
return links[a] = find(links[a]);
}
bool same(int a, int b) // check if node a and b has the same root
{
return find(a) == find(b);
}
void unite(int a, int b)
{
a = find(a);
b = find(b);
if (sizes[a] < sizes[b]) swap(a, b);
sizes[a] += sizes[b]; //a always bigger than b, move subtree b under a
links[b] = a;
}
ll get_flow(vector<vll>adj, int x, int y, int n)
{
ll ans = 0;
while (1)
{
vll dist(n), visited(n), parents(n, -1);
dist[x] = linf;
pq<pair<ll, ll>>todo; todo.push({ linf,x });
while (todo.size())
{
pair<ll, ll> temp = todo.top(); todo.pop();
F0R(i, n)
{
if (dist[i] < min(temp.f, adj[temp.s][i]))
{
dist[i] = min(temp.f, adj[temp.s][i]);
parents[i] = temp.s;
todo.push({ dist[i],i });
}
}
}
if (dist[y] == 0)break;
ans += dist[y];
int index = y;
while (index != x)
{
adj[parents[index]][index] -= dist[y];
adj[index][parents[index]] += dist[y];
index = parents[index];
}
}
return ans;
}
*/
int modInverse(int a, int m)
{
int m0 = m;
int y = 0, x = 1;
if (m == 1)
return 0;
while (a > 1)
{
// q is quotient
int q = a / m;
int t = m;
// m is remainder now, process same as
// Euclid's algo
m = a % m, a = t;
t = y;
// Update y and x
y = x - q * y;
x = t;
}
// Make x positive
if (x < 0)
x += m0;
return x;
}
ll power(ll x, ll y)
{
ll k = 1 << 30;
ll z = 1;
while (k != 0)
{
z *= z;
z %= inf;
if (y >= k)
{
z *= x;
z %= inf;
y -= k;
}
k >>= 1;
}
return z;
}
// remember that you need to take abs
long double area(pii x, pii y, pii z)
{
return ((ll)x.s * y.f + (ll)y.s * z.f + (ll)z.s * x.f - (ll)x.f * y.s - (ll)y.f * z.s - (ll)z.f * x.s) / 2.0;
}
bool clockwise(pii x, pii y, pii z)
{
return area(x, y, z) > 0;
}
struct point
{
ld x, y;
};
long double area(point x, point y, point z)
{
return (x.y * y.x + y.y * z.x + z.y * x.x - x.x * y.y - y.x * z.y - z.x * x.y) / 2.0;
}
bool clockwise(point x, point y, point z)
{
return area(x, y, z) > 0;
}
int gcd(int a, int b)
{
if (a > b)swap(a, b);
if (a == 0)return b;
return gcd(a, b % a);
}
int popcount(int a)
{
int count = 0;
while (a)
{
count += (a & 1);
a >>= 1;
}
return count;
}
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
struct custom_hash_fast {
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
x ^= FIXED_RANDOM;
return x ^ (x >> 16);
}
};
ll choose(ll n, ll r)
{
ll p = 1, k = 1;
if (n - r < r)
r = n - r;
if (r != 0) {
while (r) {
p *= n;
k *= r;
long long m = gcd(p, k);
p /= m;
k /= m;
n--;
r--;
}
}
else
p = 1;
return p;
}
//end of preprogrammed methods
void setIO(string s) {
ios_base::sync_with_stdio(0); cin.tie(0);
//freopen((s + ".in").c_str(), "r", stdin);
//freopen((s + ".out").c_str(), "w", stdout);
}
int n, root, q;
struct edge
{
ll dst, len;
};
struct node
{
int type, tin, tout;
ll depth;
pair<ll, ll> parent;
ll dist;
vector<edge> adj;
};
vector<node>tree;
int timenow;
vi depth;
void dfs(int i, int p)
{
tree[i].dist = (tree[i].type ? 0 : linf);
tree[i].tin = timenow++;
trav(x, tree[i].adj)
{
if (x.dst != p)
{
depth[x.dst] = depth[i] + 1;
tree[x.dst].depth = tree[i].depth + x.len;
tree[x.dst].parent = { i,x.len };
dfs(x.dst, i);
tree[i].dist = min(tree[i].dist, tree[x.dst].dist + x.len);
}
}
tree[i].tout = timenow++;
}
bool is_ancestor(int anc, int node)
{
return tree[anc].tin <= tree[node].tin && tree[anc].tout >= tree[node].tout;
}
int main()
{
setIO("gates");
int a;
cin >> n >> a >> q >> root; root--;
tree.rsz(n);
vector<pii>edges;
F0R(i, n - 1)
{
int a, b, c; cin >> a >> b >> c;
a--; b--;
tree[a].adj.pb({ b,c });
tree[b].adj.pb({ a,c });
edges.pb({ a,b });
}
F0R(i, a)
{
int b; cin >> b;
tree[--b].type = 1;
}
tree[root].parent = { -1, 0 };
depth.rsz(n);
dfs(root, -1);
int log = 17;
vector<vpll>jump1(n, vpll(log));// stores 2. .f is node. .s is dist
F0R(i, n)jump1[i][0] = tree[i].parent;
F0R(i, log - 1)
{
F0R(j, n)
{
if (jump1[j][i].f == -1)
jump1[j][i + 1] = { -1,0 };
else
{
pair<ll, ll> a = jump1[j][i];
if (jump1[a.f][i].f != -1)
{
jump1[j][i + 1] = { jump1[a.f][i].f,a.s + jump1[a.f][i].s };
}
else
{
jump1[j][i + 1] = { -1,0 };
}
}
}
}
vector<vll>jump(n, vll(log));// stores for each interval, the best distance one can find (like a seg tree)
jump[root][0] = tree[root].dist;
F0R(i, n)if (i != root)jump[i][0] = min(tree[i].parent.s + tree[tree[i].parent.f].dist, tree[i].dist);
F0R(i, log - 1)
{
F0R(j, n)
{
if (jump1[j][i].f == -1)
jump[j][i + 1] = linf;
else
{
pair<ll, ll> a = jump1[j][i];
if (jump1[a.f][i].f != -1)
{
jump[j][i + 1] = min(jump[j][i], jump[a.f][i] + a.s);
}
else
{
jump[j][i + 1] = linf;
}
}
}
}
F0R(i, q)
{
int index, pos; cin >> index >> pos;
index--; pos--;
int a = edges[index].f, b = edges[index].s;
if (!(is_ancestor(a, pos) && is_ancestor(b, pos)))
{
cout << "escaped" << endl;
}
else
{
if (tree[a].depth > tree[b].depth)swap(a, b);
if (tree[b].dist == linf)cout << "oo" << endl;
else
{
int curr = pos, val = 17, total = depth[pos] - depth[b];
ll ans = tree[pos].dist, dist = 0;
while (val + 1)
{
if ((1 << val) & total)
{
ans = min(ans, dist + jump[curr][val]);
dist += jump1[curr][val].s;
curr = jump1[curr][val].f;
}
val--;
}
cout << ans << endl;
}
}
}
}
Compilation message
valley.cpp: In function 'void pv(std::vector<std::vector<int> >)':
valley.cpp:21:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
| ^
valley.cpp:22:18: note: in expansion of macro 'FOR'
22 | #define F0R(i,a) FOR(i,0,a)
| ^~~
valley.cpp:58:2: note: in expansion of macro 'F0R'
58 | F0R(i, a.size()) { cout << i << endl; pv(a[i]); cout << endl; }
| ^~~
valley.cpp: In function 'void pv(std::vector<std::vector<long long int> >)':
valley.cpp:21:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
| ^
valley.cpp:22:18: note: in expansion of macro 'FOR'
22 | #define F0R(i,a) FOR(i,0,a)
| ^~~
valley.cpp:59:26: note: in expansion of macro 'F0R'
59 | }void pv(vector<vll>a) { F0R(i, a.size()) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
512 KB |
Output is correct |
| 3 |
Correct |
4 ms |
512 KB |
Output is correct |
| 4 |
Correct |
3 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
512 KB |
Output is correct |
| 3 |
Correct |
4 ms |
512 KB |
Output is correct |
| 4 |
Correct |
3 ms |
512 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1056 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 7 |
Correct |
2 ms |
928 KB |
Output is correct |
| 8 |
Correct |
2 ms |
896 KB |
Output is correct |
| 9 |
Correct |
2 ms |
896 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 11 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 12 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 14 |
Correct |
2 ms |
1024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
267 ms |
62828 KB |
Output is correct |
| 2 |
Correct |
293 ms |
62572 KB |
Output is correct |
| 3 |
Correct |
326 ms |
62700 KB |
Output is correct |
| 4 |
Correct |
385 ms |
64612 KB |
Output is correct |
| 5 |
Correct |
361 ms |
65260 KB |
Output is correct |
| 6 |
Correct |
448 ms |
69484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
512 KB |
Output is correct |
| 3 |
Correct |
4 ms |
512 KB |
Output is correct |
| 4 |
Correct |
3 ms |
512 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1056 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 7 |
Correct |
2 ms |
928 KB |
Output is correct |
| 8 |
Correct |
2 ms |
896 KB |
Output is correct |
| 9 |
Correct |
2 ms |
896 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 11 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 12 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 14 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 15 |
Correct |
267 ms |
62828 KB |
Output is correct |
| 16 |
Correct |
293 ms |
62572 KB |
Output is correct |
| 17 |
Correct |
326 ms |
62700 KB |
Output is correct |
| 18 |
Correct |
385 ms |
64612 KB |
Output is correct |
| 19 |
Correct |
361 ms |
65260 KB |
Output is correct |
| 20 |
Correct |
448 ms |
69484 KB |
Output is correct |
| 21 |
Correct |
244 ms |
64876 KB |
Output is correct |
| 22 |
Correct |
265 ms |
64492 KB |
Output is correct |
| 23 |
Correct |
290 ms |
64748 KB |
Output is correct |
| 24 |
Correct |
335 ms |
66796 KB |
Output is correct |
| 25 |
Correct |
410 ms |
69832 KB |
Output is correct |
| 26 |
Correct |
248 ms |
64884 KB |
Output is correct |
| 27 |
Correct |
270 ms |
64492 KB |
Output is correct |
| 28 |
Correct |
294 ms |
64748 KB |
Output is correct |
| 29 |
Correct |
363 ms |
66284 KB |
Output is correct |
| 30 |
Correct |
426 ms |
67824 KB |
Output is correct |
| 31 |
Correct |
250 ms |
64888 KB |
Output is correct |
| 32 |
Correct |
276 ms |
64620 KB |
Output is correct |
| 33 |
Correct |
308 ms |
64876 KB |
Output is correct |
| 34 |
Correct |
392 ms |
66828 KB |
Output is correct |
| 35 |
Correct |
412 ms |
69740 KB |
Output is correct |
| 36 |
Correct |
365 ms |
66800 KB |
Output is correct |
