QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#579237 | #5148. Tree Distance | alexz1205 | TL | 0ms | 0kb | C++14 | 5.7kb | 2024-09-21 10:53:12 | 2024-09-21 10:53:13 |
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5, Q = 1e6;
typedef long long int lint;
int n, q;
set<array<lint, 2>> con[N];
vector<array<lint, 2>> vCon[N];
lint dist[N];
lint dep[N];
array<lint, 3> queries[Q];
lint ans[Q];
/*
namespace lca{
int binJump[N][20];
bool precomp = 0;
void calcBinJump(){
for (int i = 1; i < 20; i ++){
for (int x = 0; x < n; x ++){
binJump[x][i] = binJump[binJump[x][i-1]][i-1];
}
}
precomp = 1;
}
int lca(int a, int b){
int dif = dep[a] - dep[b];
while (dif > 0){
a = binJump[a][__builtin_ctz(dif)];
dif = dep[a] - dep[b];
}
swap(a, b);
dif = dep[a] - dep[b];
while (dif > 0){
a = binJump[a][__builtin_ctz(dif)];
dif = dep[a] - dep[b];
}
if (a == b){
return a;
}
for (int x = 19; x >= 0; x --){
if (binJump[a][x] != binJump[b][x]){
a = binJump[a][x];
b = binJump[b][x];
}
}
return binJump[a][0];
}
};
lint distN(int a, int b){
int c = lca::lca(a, b);
return dist[a] + dist[b] - dist[c] - dist[c];
}
*/
namespace precomp{
void dfs(int i, int p){
//lca::binJump[i][0] = p;
for (array<lint, 2> e: vCon[i]){
if (e[0] == p) continue;
dist[e[0]] = dist[i] + e[1];
dep[e[0]] = dep[i] + 1;
dfs(e[0], i);
}
}
};
namespace decomp{
lint sz[N];
lint dist[N];
set<int> cur;
//set<array<int, 2>> nec;
set<array<lint, 3>> events;
int ind = 0;
void dfs(int i, int p){
cur.insert(i);
sz[i] = 1;
for (auto it = ::con[i].begin(); it != ::con[i].end(); ++ it){
const array<lint, 2> &e = *it;
if (e[0] == p){
continue;
}
dist[e[0]] = dist[i] + e[1];
dfs(e[0], i);
sz[i] += sz[e[0]];
}
}
int findCent(int i, int p, int s){
for (array<lint, 2> e: ::con[i]){
if (e[0] == p) continue;
//if (cent[e[0]]) continue;
if (sz[e[0]] >= sz[s]/2){
return findCent(e[0], i, s);
}
}
return i;
}
void buildDecomp(int i){
cur.clear();
dfs(i, i);
int r = findCent(i, i, i);
dist[r] = 0;
dfs(r, r);
//printf("INDEX: %d\n", r);
/*
cout << sz[i] << endl;
for (int x: cur){
cout << x << " ";
}
cout << endl;
*/
/*
set<pair<lint, int>> ord;
for (int v: cur){
//int vD = distN(v, r);
int vD = dist[v];
while (!ord.empty() && ord.rbegin()->first >= vD){
int j = ord.rbegin()->second;
//nec.insert({j, v});
ind ++;
int d = ord.rbegin()->first + vD;
events.insert({j, d, ind});
events.insert({v, d, ind});
ord.erase(--ord.end());
}
//cout << vD << " " << v << endl;
ord.insert({vD, v});
}
ord.clear();
for (auto it = cur.rbegin(); it != cur.rend(); ++ it){
int v = *it;
int vD = dist[v];
//int vD = distN(v, r);
while (!ord.empty() && ord.rbegin()->first >= vD){
int j = ord.rbegin()->second;
//nec.insert({j, v});
ind ++;
int d = ord.rbegin()->first + vD;
//int d = distN(j, v);
events.insert({j, d, ind});
events.insert({v, d, ind});
ord.erase(--ord.end());
}
//cout << vD << " " << v << endl;
ord.insert({vD, v});
}
*/
for (array<lint, 2> e: ::con[r]){
//if (cent[e[0]]) continue;
::con[e[0]].erase({r, e[1]});
buildDecomp(e[0]);
}
}
void decomp(){
buildDecomp(0);
}
};
int B;
void prep(){
scanf("%d", &n);
for (int x = 1; x < n; x ++){
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
a --, b --;
con[a].insert({b, c});
con[b].insert({a, c});
vCon[a].push_back({b, c});
vCon[b].push_back({a, c});
}
scanf("%d", &q);
for (int x = 0; x < q; x ++){
int l, r;
scanf("%d %d", &l, &r);
l --, r --;
queries[x][0] = l;
queries[x][1] = r;
queries[x][2] = x;
}
B = n/(int)sqrt(n);
sort(queries, queries + q, [](array<lint, 3> a, array<lint, 3> b){return (array<lint, 2>){a[0]/B, a[1]} < (array<lint, 2>){b[0]/B, b[1]};});
/*
for (int x = 0; x < q; x ++){
cout << queries[x][0] << " " << queries[x][1] << " " << queries[x][2] << endl;
}
*/
dep[0] = dist[0] = 0;
precomp::dfs(0, 0);
//lca::calcBinJump();
decomp::decomp();
if (n == 199999) exit(0);
/*
for (array<int, 2> p : decomp::nec){
cout << p[0] << " " << p[1] << endl;
cout << distN(p[0], p[1]) << endl;
}
for (array<lint, 3> p : decomp::events){
cout << p[0] << " " << p[1] << " " << p[2] << endl;
}
*/
}
int main(){
prep();
int l = -1;
int r = -1;
set<array<lint, 2>> rans;
lint val = 1e18;
decltype(decomp::events.begin()) at;
for (int x = 0; x < n; x ++){
int k = queries[x][2];
if ((queries[x][0]/B)*B != l){
rans.clear();
val = 1e18;
l = (queries[x][0]/B) * B;
r = l + B;
at = decomp::events.lower_bound({r, -1, -1});
}
ans[k] = 1e18;
set<array<lint, 2>> back;
if (queries[x][1] < r){
for (auto it = decomp::events.lower_bound({queries[x][0], -1, -1}); (*it)[0] <= queries[x][1]; ++ it){
if (!back.insert({(*it)[2], (*it)[1]}).second){
ans[k] = min(ans[k], (*it)[1]);
continue;
}
}
continue;
}
while ((*at)[0] <= queries[x][1]){
if (!rans.insert({(*at)[2], (*at)[1]}).second){
val = min(val, (*at)[1]);
at ++;
continue;
}
at ++;
}
ans[k] = val;
for (auto it = decomp::events.lower_bound({queries[x][0], -1, -1}); (*it)[0] < r; ++ it){
if (rans.find({(*it)[2], (*it)[1]}) != rans.end()){
ans[k] = min(ans[k], (*it)[1]);
continue;
}
if (!back.insert({(*it)[2], (*it)[1]}).second){
ans[k] = min(ans[k], (*it)[1]);
continue;
}
}
}
for (int x = 0; x < q; x ++){
if (ans[x] == 1e18) {
cout << -1 << endl;
continue;
}
cout << ans[x] << endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
5 1 2 5 1 3 3 1 4 4 3 5 2 5 1 1 1 4 2 4 3 4 2 5