#include "factories.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define rep(i, a, b) for(int (i) = (a); i <= (b); ++i)
#define repd(i, a, b) for(int (i) = (a); i >= (b); --i)
#define em emplace
#define eb emplace_back
#define fr first
#define sc second
#define mp make_pair
const char nl = '\n';
const int mxN = 5e5L + 10;
int n;
vector<pair<int, ll>> adj[mxN];
vector<pair<int, ll>> vir[mxN];
int color[mxN];
vector<int> cd[mxN];
int par[mxN];
int dep[mxN];
ll dist[mxN];
ll cX[mxN], cY[mxN];
const ll inf = 1e17L;
int tin[mxN], tout[mxN];
int tmr = 0;
int TEST = 0;
ll ans = 0;
#warning intand longlong are different
void dfs(int x, int p) {
tin[x] = tmr++;
for(auto U : adj[x]) {
int y = U.fr; ll w = U.sc;
if(y == p) continue;
par[y] = x;
dist[y] = w;
dep[y] = dep[x] + 1;
dfs(y, x);
}
tout[x] = tmr++;
/* cout << "Node: "; cout << x << ' ' << par[x] << ' ' << dist[x] << ' ' << dep[x] << ' ' << tin[x] << ' ' << tout[x] << nl; */
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
/* cout << "Edges:\n"; */
rep(i, 0, N - 2) {
/* cout << A[i] << ' ' << B[i] << ' ' << D[i] << nl; */
adj[A[i]].eb(B[i], ll(D[i]));
adj[B[i]].eb(A[i], ll(D[i]));
}
/* cout << nl; */
par[0] = -1;
dist[0] = -1;
dep[0] = 0;
dfs(0, -1);
}
int lca(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
while(dep[u] > dep[v]) {
u = par[u];
}
while(u != v) {
u = par[u];
v = par[v];
}
return u;
}
ll distance(int u, int v) {
ll res = 0;
if(dep[u] < dep[v]) swap(u, v);
while(dep[u] > dep[v]) {
res += dist[u];
u = par[u];
}
while(u != v) {
res += dist[u];
u = par[u];
res += dist[v];
v = par[v];
}
return res;
}
void print(stack<int> x) {
stack<int> y;
while(!x.empty()) {
y.push(x.top());
x.pop();
}
while(!y.empty()) {
cout << y.top() << ' ';
x.push(y.top());
y.pop();
}
cout << nl;
}
void sfd(int x, int p, ll dep) {
if(color[x] == 1) ans = min(ans, dep);
for(auto U : vir[x]) {
int y = U.fr; ll w = U.sc;
if(y == p) continue;
sfd(y, x, dep + w);
}
}
#warning make sure to reset global variablesj
long long Query(int S, int X[], int T, int Y[]) {
/* cout << nl; */
/* cout << "TESTCASE #" << ++TEST << endl; */
// clearing virtual tree first
rep(i, 0, S - 1) {
color[X[i]] = 0;
while(int(vir[X[i]].size())) vir[X[i]].pop_back();
}
rep(i, 0, T - 1) {
color[Y[i]] = 1;
while(int(vir[Y[i]].size())) vir[Y[i]].pop_back();
}
vector<int> nodes;
rep(i, 0, S - 1) nodes.eb(X[i]);
rep(i, 0, T - 1) nodes.eb(Y[i]);
sort(nodes.begin(), nodes.end(), [&](int left, int right) {
return tin[left] < tin[right];
});
/* cout << "Node order:"; */
/* for(int x : nodes) { */
/* cout << x << ' '; */
/* } */
/* cout << nl; */
/* cout << "Edges:\n"; */
int nsz = S + T;
while(nsz > 1) {
int r = nsz - 1;
int l = nsz - 2;
if(tin[nodes[l]] < tin[nodes[r]] && tout[nodes[r]] < tout[nodes[l]]) {
ll distlr = distance(nodes[r], nodes[l]);
vir[nodes[r]].eb(nodes[l], distlr);
vir[nodes[l]].eb(nodes[r], distlr);
/* cout << nodes[l] << ' ' << nodes[r] << ' ' << distlr << nl; */
nodes.pop_back(); --nsz;
continue;
}
int anc = lca(nodes[r], nodes[l]);
color[anc] = -1;
while(int(vir[anc].size())) vir[anc].pop_back();
ll distal = distance(nodes[l], anc);
vir[anc].eb(nodes[l], distal);
vir[nodes[l]].eb(anc, distal);
/* cout << anc << ' ' << nodes[l] << ' ' << distal << nl; */
nodes.pop_back(); --nsz;
ll distar = distance(nodes[r], anc);
vir[anc].eb(nodes[r], distar);
vir[nodes[r]].eb(anc, distar);
/* cout << anc << ' ' << nodes[r] << ' ' << distar << nl; */
l -= 1;
/* cout << "check:" << l << ' ' << nodes[l] << ' ' << anc << nl; */
while(nsz > 0 && tin[anc] < tin[nodes[l]] && tout[nodes[l]] < tout[anc]) {
/* cout << "check2:" << l << ' ' << nodes[l] << ' ' << anc << nl; */
distal = distance(nodes[l], anc);
vir[anc].eb(nodes[l], distal);
vir[nodes[l]].eb(anc, distal);
/* cout << anc << ' ' << nodes[l] << ' ' << distal << nl; */
nodes.pop_back(); --nsz;
--l;
/* cout << "check:" << l << ' ' << nodes[l] << ' ' << anc << nl; */
}
/* cout << nl; */
}
ans = inf;
rep(i, 0, S - 1) {
sfd(X[i], -1, 0);
}
return ans;
#warning returning zero
return 0;
}
Compilation message
factories.cpp:37:2: warning: #warning intand longlong are different [-Wcpp]
37 | #warning intand longlong are different
| ^~~~~~~
factories.cpp:119:2: warning: #warning make sure to reset global variablesj [-Wcpp]
119 | #warning make sure to reset global variablesj
| ^~~~~~~
factories.cpp:194:2: warning: #warning returning zero [-Wcpp]
194 | #warning returning zero
| ^~~~~~~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:6:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
6 | #define rep(i, a, b) for(int (i) = (a); i <= (b); ++i)
| ^
factories.cpp:56:5: note: in expansion of macro 'rep'
56 | rep(i, 0, N - 2) {
| ^~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:6:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
6 | #define rep(i, a, b) for(int (i) = (a); i <= (b); ++i)
| ^
factories.cpp:124:5: note: in expansion of macro 'rep'
124 | rep(i, 0, S - 1) {
| ^~~
factories.cpp:6:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
6 | #define rep(i, a, b) for(int (i) = (a); i <= (b); ++i)
| ^
factories.cpp:128:5: note: in expansion of macro 'rep'
128 | rep(i, 0, T - 1) {
| ^~~
factories.cpp:6:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
6 | #define rep(i, a, b) for(int (i) = (a); i <= (b); ++i)
| ^
factories.cpp:134:5: note: in expansion of macro 'rep'
134 | rep(i, 0, S - 1) nodes.eb(X[i]);
| ^~~
factories.cpp:6:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
6 | #define rep(i, a, b) for(int (i) = (a); i <= (b); ++i)
| ^
factories.cpp:135:5: note: in expansion of macro 'rep'
135 | rep(i, 0, T - 1) nodes.eb(Y[i]);
| ^~~
factories.cpp:6:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
6 | #define rep(i, a, b) for(int (i) = (a); i <= (b); ++i)
| ^
factories.cpp:190:5: note: in expansion of macro 'rep'
190 | rep(i, 0, S - 1) {
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
64236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
64104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
64236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
