#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const ll N = 5e5 + 5, oo = 1e18 + 7, mod = 1e9 + 7;
ll n;
vector<pair<ll, ll>> Adj[N];
ll d1[N], d2[N];
ll anc[N][20];
//dist[N][20];
void dfs(int u, int p){
for(auto it : Adj[u]){
int v = it.fi, w = it.se;
if(v == p) continue;
d1[v] = d1[u] + 1;
d2[v] = d2[u] + w;
anc[v][0] = u;
//dist[v][0] = w;
dfs(v, u);
}
}
void prep(){
for(int i = 1; i <= 19; i++){
for(int j = 1; j <= n; j++){
anc[j][i] = anc[anc[j][i - 1]][i - 1];
//dist[j][i] = dist[j][i - 1] + dist[anc[j][i - 1]][i - 1];
}
}
}
int lca(int x, int y){
if(d1[x] > d1[y]) swap(x, y);
for(int i = 19; i >= 0; i--){
if((d1[x] + (1LL << i)) <= d1[y]) y = anc[y][i];
}
if(x == y) return x;
for(int i = 19; i >= 0; i--){
if(anc[x][i] != anc[y][i]){
x = anc[x][i], y = anc[y][i];
}
}
return anc[x][0];
}
ll dist(int x, int y){
return d2[x] + d2[y] - 2 * d2[lca(x, y)];
}
int cnt;
int pos[N], l[N], r[N];
int arr[N];
void pre_dfs(int u, int p){
cnt++;
pos[u] = l[u] = cnt;
arr[cnt] = u;
for(auto it : Adj[u]){
int v = it.fi;
if(v == p) continue;
pre_dfs(v, u);
}
r[u] = cnt;
}
void Init(int N, int A[], int B[], int D[]){
n = N;
for(int i = 0; i < (n - 1); i++){
Adj[A[i] + 1].pb({B[i] + 1, D[i]});
Adj[B[i] + 1].pb({A[i] + 1, D[i]});
}
pre_dfs(1, 1);
dfs(1, 1);
prep();
}
bool choose1[N], choose2[N];
int IT[N << 2];
vector<int> vis;
void upd(int id, int l, int r, int L, int R, int val){
vis.pb(id);
if(l > R || r < L) return;
if(l >= L && r <= R){
IT[id] = val;
return;
}
if(IT[id]){
IT[id << 1] = IT[id << 1 | 1] = IT[id];
IT[id] = 0;
}
int mid = (l + r) >> 1;
upd(id << 1, l, mid, L, R, val);
upd(id << 1 | 1, mid + 1, r, L, R, val);
}
int get(int id, int l, int r, int pos){
vis.pb(id);
if(l == r){
return IT[id];
}
if(IT[id]){
IT[id << 1] = IT[id << 1 | 1] = IT[id];
IT[id] = 0;
}
int mid = (l + r) >> 1;
if(pos <= mid) return get(id << 1, l, mid, pos);
else return get(id << 1 | 1, mid + 1, r, pos);
}
int sub[N];
ll Query(int S, int X[], int T, int Y[]){
vis.clear();
// build the subtree part
vector<pair<ll, ll>> nodes;
for(int i = 0; i < S; i++) nodes.pb({d2[X[i] + 1], X[i] + 1});
sort(nodes.begin(), nodes.end());
vector<pair<ll, ll>> queries;
int cnt = -1;
bool ck = 0;
for(auto it : nodes){
cnt++;
ll u = it.se;
ll temp = get(1, 1, n, pos[u]), temp3 = u;
if(!cnt) temp3 = 1;
else{
ll xx = lca(temp, u);
ll temp2 = dist(temp, xx);
for(int i = 19; i >= 0; i--){
int x = anc[temp3][i];
if(!x) continue;
if(dist(u, x) < dist(temp, x)) temp3 = x;
//if((temp2 + (d2[x] - d[xx])) > (d2[u] - d2[x])) temp3 = x;
}
}
assert(d2[u] >= d2[temp] || temp3 == 1);
sub[u] = temp3;
upd(1, 1, n, l[temp3], r[temp3], u);
if(temp3 == 1) ck = 1;
queries.pb({l[temp3], cnt});
queries.pb({r[temp3] + 1, cnt});
}
assert(ck);
sort(queries.begin(), queries.end());
set<ll> cur;
// process part
vector<ii> nodes2;
for(int i = 0; i < T; i++) nodes2.pb({pos[Y[i] + 1], Y[i] + 1});
sort(nodes2.begin(), nodes2.end());
int itr = 0;
ll answer = oo;
for(auto it : nodes2){
while(itr < queries.size() && queries[itr].fi <= it.fi){
if(cur.find(queries[itr].se) != cur.end()) cur.erase(queries[itr].se);
else cur.insert(queries[itr].se);
itr++;
}
//assert(itr < queries.size());
//assert(cur.size());
//int temp = 1;
int temp = (*cur.rbegin());
assert(temp < nodes.size());
answer = min(answer, dist(it.se, nodes[temp].se));
}
for(auto it : vis) IT[it] = 0;
return answer;
/*
if(S <= 5000 && T <= 5000){
ll ans = oo;
for(int i = 0; i < S; i++){
for(int j = 0; j < T; j++) ans = min(ans, dist(X[i] + 1, Y[j] + 1));
}
return ans;
}
else{
answer = oo;
//vis.clear();
for(int i = 0; i < S; i++) choose1[X[i] + 1] = 1;
for(int i = 0; i < T; i++) choose2[Y[i] + 1] = 1;
ini(1, 1, n);
main_dfs(1, 1);
for(int i = 0; i < S; i++) choose1[X[i] + 1] = 0;
for(int i = 0; i < T; i++) choose2[Y[i] + 1] = 0;
return answer;
//vis.clear();
}*/
}
/*
void process(){
int n, q;
vector<int> a(n - 1), b(n - 1), d(n - 1);
cin >> n >> q;
for(int i = 0; i < (n - 1); i++){
cin >> a[i] >> b[i] >> d[i];
}
Init(n, a, b, d);
while(q--){
int sz1, sz2;
vector<int> vc1, vc2;
cin >> sz1 >> sz2;
vc1.resize(sz1);
for(int i = 0; i < sz1; i++) cin >> vc1[i];
vc2.resize(sz2);
for(int i = 0; i < sz2; i++) cin >> vc2[i];
cout << Query(sz1, vc1, sz2, vc2) << "\n";
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
process();
}*/
Compilation message
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:145:16: warning: unused variable 'temp2' [-Wunused-variable]
145 | ll temp2 = dist(temp, xx);
| ^~~~~
factories.cpp:170:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
170 | while(itr < queries.size() && queries[itr].fi <= it.fi){
| ~~~~^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from factories.cpp:1:
factories.cpp:179:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
179 | assert(temp < nodes.size());
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
12556 KB |
Output is correct |
| 2 |
Correct |
1539 ms |
21808 KB |
Output is correct |
| 3 |
Correct |
2153 ms |
21644 KB |
Output is correct |
| 4 |
Correct |
1979 ms |
22720 KB |
Output is correct |
| 5 |
Correct |
2768 ms |
22480 KB |
Output is correct |
| 6 |
Correct |
1229 ms |
21832 KB |
Output is correct |
| 7 |
Correct |
2118 ms |
21584 KB |
Output is correct |
| 8 |
Correct |
2162 ms |
21688 KB |
Output is correct |
| 9 |
Correct |
2544 ms |
22364 KB |
Output is correct |
| 10 |
Correct |
1049 ms |
21832 KB |
Output is correct |
| 11 |
Correct |
2033 ms |
21792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
12352 KB |
Output is correct |
| 2 |
Correct |
2221 ms |
150424 KB |
Output is correct |
| 3 |
Correct |
6396 ms |
154400 KB |
Output is correct |
| 4 |
Correct |
1435 ms |
148144 KB |
Output is correct |
| 5 |
Correct |
7879 ms |
184740 KB |
Output is correct |
| 6 |
Correct |
6403 ms |
155708 KB |
Output is correct |
| 7 |
Correct |
5545 ms |
48824 KB |
Output is correct |
| 8 |
Correct |
1728 ms |
48588 KB |
Output is correct |
| 9 |
Execution timed out |
8055 ms |
52096 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
12556 KB |
Output is correct |
| 2 |
Correct |
1539 ms |
21808 KB |
Output is correct |
| 3 |
Correct |
2153 ms |
21644 KB |
Output is correct |
| 4 |
Correct |
1979 ms |
22720 KB |
Output is correct |
| 5 |
Correct |
2768 ms |
22480 KB |
Output is correct |
| 6 |
Correct |
1229 ms |
21832 KB |
Output is correct |
| 7 |
Correct |
2118 ms |
21584 KB |
Output is correct |
| 8 |
Correct |
2162 ms |
21688 KB |
Output is correct |
| 9 |
Correct |
2544 ms |
22364 KB |
Output is correct |
| 10 |
Correct |
1049 ms |
21832 KB |
Output is correct |
| 11 |
Correct |
2033 ms |
21792 KB |
Output is correct |
| 12 |
Correct |
10 ms |
12352 KB |
Output is correct |
| 13 |
Correct |
2221 ms |
150424 KB |
Output is correct |
| 14 |
Correct |
6396 ms |
154400 KB |
Output is correct |
| 15 |
Correct |
1435 ms |
148144 KB |
Output is correct |
| 16 |
Correct |
7879 ms |
184740 KB |
Output is correct |
| 17 |
Correct |
6403 ms |
155708 KB |
Output is correct |
| 18 |
Correct |
5545 ms |
48824 KB |
Output is correct |
| 19 |
Correct |
1728 ms |
48588 KB |
Output is correct |
| 20 |
Execution timed out |
8055 ms |
52096 KB |
Time limit exceeded |
| 21 |
Halted |
0 ms |
0 KB |
- |
