/*
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 = 19;
const int MAX = 5e5 + 5;
int n;
vpi adj[MAX];
int visited[MAX], sizes[MAX], parent[MAX];
ll dist[MAX][SZ];
int temp[MAX];
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 get_dist(int i, int p, ll d)
{
dist[i][temp[i]++] = d;
trav(x, adj[i])
{
if (x.f == p || visited[x.f])continue;
get_dist(x.f, i, d + x.s);
}
}
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]);
get_dist(centroid, -1, 0);
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()
{
F0R(i, n)visited[i] = 0, sizes[i] = 0, parent[i] = 0;
build(0, -1);
}
};
ll dp[MAX];
centroid g;
//lca<SZ> g1;
//ll dist[MAX][SZ];
void Init(int N, int A[], int B[], int D[])
{
n = N;
F0R(i, n - 1)
{
adj[A[i]].pb({ B[i],D[i] });
adj[B[i]].pb({ A[i],D[i] });
}
F0R(i, n)temp[i] = 0;
g.init();
//g1.init();
F0R(i, n)dp[i] = linf;
}
long long Query(int S, int X[], int T, int Y[])
{
ll ans = linf;
F0R(i, S)
{
int x = X[i], t = X[i];
int j = temp[x] - 1;
while (t != -1)
{
dp[t] = min(dp[t], dist[x][j--]);
t = parent[t];
}
}
F0R(i, T)
{
int x = Y[i], t = Y[i];
int j = temp[x] - 1;
while (t != -1)
{
ans = min(ans, dp[t] + dist[x][j--]);
t = parent[t];
}
}
F0R(i, S)
{
int x = X[i], t = X[i];
int j = 0;
while (t != -1)
{
dp[t] = linf;
t = parent[t];
}
}
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 'long long int Query(int, int*, int, int*)':
factories.cpp:175:7: warning: unused variable 'x' [-Wunused-variable]
175 | int x = X[i], t = X[i];
| ^
factories.cpp:176:7: warning: unused variable 'j' [-Wunused-variable]
176 | int j = 0;
| ^
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 |
16 ms |
12524 KB |
Output is correct |
| 2 |
Correct |
343 ms |
21228 KB |
Output is correct |
| 3 |
Correct |
372 ms |
21228 KB |
Output is correct |
| 4 |
Correct |
383 ms |
21500 KB |
Output is correct |
| 5 |
Correct |
410 ms |
21516 KB |
Output is correct |
| 6 |
Correct |
273 ms |
21228 KB |
Output is correct |
| 7 |
Correct |
404 ms |
21228 KB |
Output is correct |
| 8 |
Correct |
369 ms |
21228 KB |
Output is correct |
| 9 |
Correct |
386 ms |
21484 KB |
Output is correct |
| 10 |
Correct |
270 ms |
21228 KB |
Output is correct |
| 11 |
Correct |
366 ms |
21228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
12268 KB |
Output is correct |
| 2 |
Correct |
2143 ms |
129652 KB |
Output is correct |
| 3 |
Incorrect |
3405 ms |
132176 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
12524 KB |
Output is correct |
| 2 |
Correct |
343 ms |
21228 KB |
Output is correct |
| 3 |
Correct |
372 ms |
21228 KB |
Output is correct |
| 4 |
Correct |
383 ms |
21500 KB |
Output is correct |
| 5 |
Correct |
410 ms |
21516 KB |
Output is correct |
| 6 |
Correct |
273 ms |
21228 KB |
Output is correct |
| 7 |
Correct |
404 ms |
21228 KB |
Output is correct |
| 8 |
Correct |
369 ms |
21228 KB |
Output is correct |
| 9 |
Correct |
386 ms |
21484 KB |
Output is correct |
| 10 |
Correct |
270 ms |
21228 KB |
Output is correct |
| 11 |
Correct |
366 ms |
21228 KB |
Output is correct |
| 12 |
Correct |
10 ms |
12268 KB |
Output is correct |
| 13 |
Correct |
2143 ms |
129652 KB |
Output is correct |
| 14 |
Incorrect |
3405 ms |
132176 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
