#include "factories.h"
#include <bits/stdc++.h>
#define ll long long
#define FOR(i,x,y) for(ll i=x; i<y; i++)
using namespace std;
bool r[600000];
vector<pair<ll,ll>> edges[600000];
ll sub[600000], par[600000], ans[600000];
ll n,m,root;
ll tree[2097152];
ll first[600000];
ll dists[600000];
vector<ll> euler;
vector<ll> updated;
void dfs2(ll a, ll p, ll v){
dists[a] = v;
euler.push_back(a);
for (auto&i : edges[a]){
if (i.first!=p){
euler.push_back(a);
dfs2(i.first, a, v+i.second);
}
}
}
void update(ll a, ll k){
a += 1048576;
tree[a] = k;
while (a){
a/=2;
tree[a] = dists[tree[2*a]] < dists[tree[2*a+1]] ? tree[2*a] : tree[2*a+1];
}
}
ll query(ll a, ll b, ll k=1, ll x=0, ll y = 1048576-1){
//cout << a<<" "<<b<<" "<<x << " " << y << " "<<k<< endl;
if (b<x || a>y) return 0;
if (a<=x && y<=b){
return tree[k];
}
ll d = (x+y)/2;
ll sus = query(a,b,2*k,x,d);
ll sussy = query(a,b,2*k+1,d+1,y);
if (dists[sus] < dists[sussy]) return sus;
return sussy;
}
ll dfs(ll a, ll p){
sub[a] = 1;
for (auto& i : edges[a]){
if (i.first!=p && !r[i.first]) sub[a] += dfs(i.first, a);
}
return sub[a];
}
ll centroid(ll a, ll sz, ll p){
for (auto&i : edges[a]){
if (i.first!=p && !r[i.first] && sub[i.first]*2 > sz){
return centroid(i.first, sz, a);
}
}
return a;
}
void decomp(ll a, ll p){
ll c = centroid(a, dfs(a, -1), -1);
if (p!=-1){
par[c] = p;
}else{
par[c] = -1;
}
r[c] = 1;
for (auto&i : edges[c]){
if (!r[i.first]) decomp(i.first, c);
}
}
ll dist(ll a, ll b){
if (first[a] > first[b]) swap(a,b);
return dists[a] + dists[b] - 2*dists[query(first[a],first[b])];
}
void update(ll a){
ll orig = a;
ans[a] = 0;
updated.push_back(a);
ll distance = 0;
while (par[a] != -1){
distance = dist(orig, par[a]);
a = par[a];
ans[a] = min(ans[a], distance);
updated.push_back(a);
}
}
ll query(ll a){
ll orig = a;
ll distance = 0;
ll tempans = 1000000000000000;
tempans = min(tempans, ans[a]);
while (par[a] != -1){
distance = dist(orig, par[a]);
a = par[a];
tempans = min(tempans, distance + ans[a]);
}
return tempans;
}
void Init(int N, int A[], int B[], int D[]) {
FOR(i,0,1048576) tree[i] = 0;
FOR(i,0,600000) sub[i] = 0, r[i] = 0, ans[i] = 1000000000000000;
n = N;
dists[0] = 1000000000000000;
FOR(i,0,n-1){
ll a,b,c;
a = A[i]+1;
b = B[i]+1;
c = D[i];
edges[a].push_back(make_pair(b,c));
edges[b].push_back(make_pair(a,c));
}
dfs2(1,-1,0);
cout << 3 << endl;
cout << euler.size() << endl;
FOR(i,0,euler.size()){
update(i, euler[i]);
}
decomp(1,-1);
}
long long Query(int S, int X[], int T, int Y[]) {
return 0;
updated.clear();
ll anss = 1000000000000000;
FOR(i,0,S){
update(X[i]+1);
}
FOR(i,0,T){
anss = min(anss, (ll) query(Y[i]+1));
}
for (auto&i : updated){
ans[i] = 1000000000000000;
}
return anss;
}
Compilation message
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:5:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
165 | FOR(i,0,euler.size()){
| ~~~~~~~~~~~~~~~~
factories.cpp:165:3: note: in expansion of macro 'FOR'
165 | FOR(i,0,euler.size()){
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
32852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
32732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
32852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
