#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
//#include <unordered_map>
//#include <unordered_set>
#include <vector>
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;
#define mp make_pair
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
#define ldb ldouble
typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;
int IT_MAX = 1 << 17;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#include "factories.h"
bool dchk[500050];
int dep[500050];
int lr[500050][2];
ll par[500050][20][2];
int tus;
vector <pll> conn[500050];
void DFS(int n) {
dchk[n] = true;
lr[n][0] = ++tus;
for (auto it : conn[n]) {
if (dchk[it.second]) continue;
par[it.second][0][0] = n, par[it.second][0][1] = it.first;
for (int i = 1; i <= 19; i++) {
int tp = par[it.second][i - 1][0];
par[it.second][i][0] = par[tp][i - 1][0];
par[it.second][i][1] = par[it.second][i - 1][1] + par[tp][i - 1][1];
}
dep[it.second] = dep[n] + 1;
DFS(it.second);
}
lr[n][1] = tus;
}
pll lca(int a, int b) {
pll rv = pll(0, 0);
if (dep[a] > dep[b]) swap(a, b);
int c = dep[b] - dep[a];
for (int i = 19; i >= 0; i--) {
if (c & (1 << i)) {
rv.first += par[b][i][1];
b = par[b][i][0];
}
}
if (a == b) return pll(rv.first, a);
for (int i = 19; i >= 0; i--) {
if (par[a][i][0] != par[b][i][0]) {
rv.first += par[a][i][1];
rv.first += par[b][i][1];
a = par[a][i][0];
b = par[b][i][0];
}
}
rv.first += par[a][0][1];
rv.first += par[b][0][1];
return pll(rv.first, par[a][0][0]);
}
void Init(int N, int A[], int B[], int D[]) {
int i, j;
for (i = 0; i <= N - 2; i++) {
conn[A[i]].emplace_back(D[i], B[i]);
conn[B[i]].emplace_back(D[i], A[i]);
}
tus = 0;
DFS(0);
}
class Node {
public:
ll mn, v;
Node() {
*this = Node(0, 0);
}
Node(ll mn, ll v) : mn(mn), v(v) {}
};
Node indt[1100000];
void propagate(int n) {
indt[2 * n].v += indt[n].v;
indt[2 * n].mn += indt[n].v;
indt[2 * n + 1].v += indt[n].v;
indt[2 * n + 1].mn += indt[n].v;
indt[n].v = 0;
}
void update(int st, int en, int S, int E, int n, ll v) {
if (st > en) return;
if (st == S && en == E) {
indt[n].v += v;
indt[n].mn += v;
return;
}
propagate(n);
int M = (S + E) / 2;
update(st, min(en, M), S, M, 2 * n, v);
update(max(M + 1, st), en, M + 1, E, 2 * n + 1, v);
indt[n].mn = min(indt[2 * n].mn, indt[2 * n + 1].mn);
}
ll getmn(int st, int en, int S, int E, int n) {
if (st > en) return LL_INF;
if (st == S && en == E) return indt[n].mn;
propagate(n);
int M = (S + E) / 2;
return min(getmn(st, min(en, M), S, M, 2 * n), getmn(max(st, M + 1), en, M + 1, E, 2 * n + 1));
}
ll qans;
vector <int> Vv;
vector <pll> conn2[500050];
vector <pll> son2[500050];
ll dis[500050];
int lr2[500050][2];
int tchk[500050];
void DFS2(int n) {
dchk[n] = true;
lr2[n][0] = ++tus;
for (auto it : conn2[n]) {
if (dchk[it.second]) continue;
son2[n].push_back(it);
dis[it.second] = dis[n] + it.first;
DFS2(it.second);
}
lr2[n][1] = tus;
}
void DFS3(int n) {
if (tchk[n] == 1) qans = min(qans, getmn(1, Vv.size(), 1, IT_MAX, 1));
for (auto it : son2[n]) {
update(1, Vv.size(), 1, IT_MAX, 1, it.first);
update(lr2[it.second][0], lr2[it.second][1], 1, IT_MAX, 1, -2 * it.first);
DFS3(it.second);
update(1, Vv.size(), 1, IT_MAX, 1, -it.first);
update(lr2[it.second][0], lr2[it.second][1], 1, IT_MAX, 1, 2 * it.first);
}
}
long long Query(int S, int X[], int T, int Y[]) {
int i, j;
for (i = 0; i < S; i++) Vv.push_back(X[i]);
for (i = 0; i < T; i++) Vv.push_back(Y[i]);
sort(all(Vv), [](int a, int b) {
return lr[a][0] < lr[b][0];
});
vector <int> Vv2;
for (i = 0; i + 1 < Vv.size(); i++) Vv2.push_back(lca(Vv[i], Vv[i + 1]).second);
for (auto it : Vv2) Vv.push_back(it);
sort(all(Vv), [](int a, int b) {
return lr[a][0] < lr[b][0];
});
Vv.erase(unique(all(Vv)), Vv.end());
for (auto it : Vv) tchk[it] = 0;
for (i = 0; i < S; i++) tchk[X[i]] = 1;
for (i = 0; i < T; i++) tchk[Y[i]] = -1;
for (i = 0; i + 1 < Vv.size(); i++) {
int x = Vv[i];
int y = Vv[i + 1];
x = lca(x, y).second;
pll u = lca(x, y);
conn2[x].emplace_back(u.first, y);
conn2[y].emplace_back(u.first, x);
}
for (i = 0; i < Vv.size(); i++) {
dchk[Vv[i]] = false;
dis[Vv[i]] = 0;
}
tus = 0;
DFS2(Vv[0]);
for (IT_MAX = 2; IT_MAX <= Vv.size(); IT_MAX *= 2);
for (i = 1; i < 2 * IT_MAX; i++) indt[i] = Node(0, 0);
for (i = 0; i < Vv.size(); i++) {
ll v = dis[Vv[i]];
if (tchk[Vv[i]] != -1) v = LL_INF;
update(lr2[Vv[i]][0], lr2[Vv[i]][0], 1, IT_MAX, 1, v);
}
qans = LL_INF;
DFS3(Vv[0]);
for (auto it : Vv) {
conn2[it].clear();
son2[it].clear();
}
Vv.clear();
return qans;
}
Compilation message
factories.cpp:23:0: warning: ignoring #pragma warning [-Wunknown-pragmas]
#pragma warning(disable:4996)
^
factories.cpp:24:0: warning: ignoring #pragma comment [-Wunknown-pragmas]
#pragma comment(linker, "/STACK:336777216")
^
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:102:9: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:188:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i + 1 < Vv.size(); i++) Vv2.push_back(lca(Vv[i], Vv[i + 1]).second);
^
factories.cpp:198:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i + 1 < Vv.size(); i++) {
^
factories.cpp:207:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < Vv.size(); i++) {
^
factories.cpp:213:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (IT_MAX = 2; IT_MAX <= Vv.size(); IT_MAX *= 2);
^
factories.cpp:215:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < Vv.size(); i++) {
^
factories.cpp:180:9: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
249156 KB |
Output is correct |
| 2 |
Correct |
4186 ms |
249820 KB |
Output is correct |
| 3 |
Correct |
5093 ms |
249684 KB |
Output is correct |
| 4 |
Correct |
4513 ms |
249876 KB |
Output is correct |
| 5 |
Correct |
3809 ms |
249760 KB |
Output is correct |
| 6 |
Correct |
3309 ms |
249612 KB |
Output is correct |
| 7 |
Correct |
5189 ms |
249684 KB |
Output is correct |
| 8 |
Correct |
4613 ms |
249840 KB |
Output is correct |
| 9 |
Correct |
3849 ms |
249764 KB |
Output is correct |
| 10 |
Correct |
3059 ms |
249612 KB |
Output is correct |
| 11 |
Correct |
5223 ms |
249684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
249156 KB |
Output is correct |
| 2 |
Correct |
4329 ms |
288988 KB |
Output is correct |
| 3 |
Execution timed out |
6000 ms |
294212 KB |
Execution timed out |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6000 ms |
303528 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
