/*
ID: awesome35
LANG: C++14
TASK: vans
*/
#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 pair<ll, ll> pll;
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 testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 998244353;//1000000007
const ld pi = 3.1415926535;
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, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
ios_base::sync_with_stdio(0); cin.tie(0);
if (sz(s))
{
freopen((s + ".in").c_str(), "r", stdin);
if (s != "test1")
freopen((s + ".out").c_str(), "w", stdout);
}
}
/**/
#ifndef arwaeystoamneg
#include "factories.h"
#endif
const int SZ = 20;
int n;
vector<vpi>adj;
vi visited, sizes, parent;
struct centroid
{
void dfs(int i, int p)
{
// visit i
sizes[i] = 1;
for (auto x : adj[i])
{
if (x.f == p || visited[i] == 1)
continue;
dfs(x.f, i);
sizes[i] += sizes[x.f];
}
}
int dfs_centroid(int i, int p, int n)
{
// visit i, find the centroid c
// recurrent if i has a subtree larger than n/2;
for (auto x : adj[i])
{
if (x.f == p)
continue;
if (sizes[x.f] > n / 2)
return dfs_centroid(x.f, i, n);
}
return i;
}
void build(int i, int p)
{
// first dfs to generate size of subtree starting from node i
// 2nd dfs to find the centroid
dfs(i, p);
int centroid = dfs_centroid(i, p, sizes[i]);
visited[centroid] = 1;
parent[centroid] = p;
//cout << centroid << endl;
// remove the edge from centroid to all its child, build from its child
for (auto x : adj[centroid])
{
if (x.f == parent[centroid])
continue;
//cout << "working on subtree of " << x << endl;
if (visited[x.f])
continue;
build(x.f, centroid);
}
}
void init()
{
visited.rsz(n);
sizes.rsz(n);
parent.rsz(n);
build(0, -1);
}
};
template<int SZ>struct lca
{
vector<vi>jump;
vi parent, depth;
vll dist;
void dfs(int i, int p)
{
parent[i] = p;
trav(x, adj[i])
{
if (x.f == p)continue;
depth[x.f] = depth[i] + 1;
dist[x.f] = dist[i] + x.s;
dfs(x.f, i);
}
}
void init()
{
parent.rsz(n);
depth.rsz(n);
dist.rsz(n);
dfs(0, -1);
jump.rsz(n, vi(SZ));
F0R(i, n)jump[i][0] = parent[i];
F0R(i, SZ - 1)
{
F0R(j, n)jump[j][i + 1] = (jump[j][i] == -1 ? -1 : jump[jump[j][i]][i]);
}
}
int get(int a, int b)
{
F0R(j, SZ)
{
if (b & (1 << j))
{
a = jump[a][j];
}
}
return a;
}
int LCA(int a, int b)
{
if (depth[a] < depth[b])swap(a, b);
a = get(a, depth[a] - depth[b]);
if (a == b)return a;
int j = SZ;
while (j)
{
j--;
int ta = jump[a][j], tb = jump[b][j];
if (ta != tb)a = ta, b = tb;
}
return parent[a];
}
ll val(int a, int b)
{
return dist[a] + dist[b] - 2 * dist[LCA(a, b)];
}
};
vll dp;
centroid g;
lca<SZ> g1;
const int MAX = 5e5 + 5;
//ll dist[MAX][SZ];
vector<vll>dist;
void Init(int N, int A[], int B[], int D[])
{
n = N;
adj.rsz(n);
F0R(i, n - 1)
{
adj[A[i]].pb({ B[i],D[i] });
adj[B[i]].pb({ A[i],D[i] });
}
g.init();
g1.init();
dp.rsz(n, linf);
dist.rsz(n);
F0R(i, n)
{
int t = i;
while (t != -1)
{
dist[i].pb(g1.val(t, i));
t = parent[t];
}
}
}
long long Query(int S, int X[], int T, int Y[])
{
ll ans = linf;
vector<int> todo;
F0R(i, S)
{
int x = X[i], t = X[i];
int j = 0;
while (t != -1)
{
dp[t] = min(dp[t], dist[x][j++]);
todo.pb(t);
t = parent[t];
}
}
F0R(i, T)
{
int x = Y[i], t = Y[i];
int j = 0;
while (t != -1)
{
ans = min(ans, dp[t] + dist[x][j++]);
t = parent[t];
}
}
trav(x, todo)dp[x] = linf;
return ans;
}
#ifdef arwaeystoamneg
int main()
{
setIO("test1");
int n, q;
cin >> n >> q;
int A[MAX], B[MAX], D[MAX], X[MAX], Y[MAX];
F0R(i, n - 1)cin >> A[i] >> B[i] >> D[i];
Init(n, A, B, D);
while (q--)
{
int s, t;
cin >> s >> t;
F0R(i, s)cin >> X[i];
F0R(i, t)cin >> Y[i];
cout << Query(s, X, t, Y) << endl;
}
}
#endif
Compilation message
factories.cpp: In function 'void setIO(std::string)':
factories.cpp:53:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
53 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
factories.cpp:55:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
55 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
1004 KB |
Output is correct |
| 2 |
Correct |
358 ms |
13676 KB |
Output is correct |
| 3 |
Correct |
390 ms |
13816 KB |
Output is correct |
| 4 |
Correct |
406 ms |
14404 KB |
Output is correct |
| 5 |
Correct |
436 ms |
14596 KB |
Output is correct |
| 6 |
Correct |
268 ms |
13624 KB |
Output is correct |
| 7 |
Correct |
406 ms |
14028 KB |
Output is correct |
| 8 |
Correct |
397 ms |
14128 KB |
Output is correct |
| 9 |
Correct |
476 ms |
14604 KB |
Output is correct |
| 10 |
Correct |
299 ms |
13624 KB |
Output is correct |
| 11 |
Correct |
396 ms |
14116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
620 KB |
Output is correct |
| 2 |
Correct |
3447 ms |
197988 KB |
Output is correct |
| 3 |
Execution timed out |
8035 ms |
236640 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
1004 KB |
Output is correct |
| 2 |
Correct |
358 ms |
13676 KB |
Output is correct |
| 3 |
Correct |
390 ms |
13816 KB |
Output is correct |
| 4 |
Correct |
406 ms |
14404 KB |
Output is correct |
| 5 |
Correct |
436 ms |
14596 KB |
Output is correct |
| 6 |
Correct |
268 ms |
13624 KB |
Output is correct |
| 7 |
Correct |
406 ms |
14028 KB |
Output is correct |
| 8 |
Correct |
397 ms |
14128 KB |
Output is correct |
| 9 |
Correct |
476 ms |
14604 KB |
Output is correct |
| 10 |
Correct |
299 ms |
13624 KB |
Output is correct |
| 11 |
Correct |
396 ms |
14116 KB |
Output is correct |
| 12 |
Correct |
2 ms |
620 KB |
Output is correct |
| 13 |
Correct |
3447 ms |
197988 KB |
Output is correct |
| 14 |
Execution timed out |
8035 ms |
236640 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
