QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#584024 | #5148. Tree Distance | alexz1205 | WA | 0ms | 18712kb | C++17 | 4.7kb | 2024-09-23 04:23:15 | 2024-09-23 04:23:16 |
Judging History
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];
array<lint, 3> queries[Q];
lint ans[Q];
namespace decomp{
int ind2 = 0;
array<lint, 3> events[(int)8e6];
//vector<array<lint, 3>> events;
lint sz[N];
lint dist[N];
vector<int> cur;
int ind = 0;
vector<array<lint, 2>> ord;
void dfs(int i, int p){
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;
}
dfs(e[0], i);
sz[i] += sz[e[0]];
}
}
void dat(int i, int p){
cur.push_back(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];
dat(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 (sz[e[0]] >= sz[s]/2){
return findCent(e[0], i, s);
}
}
return i;
}
void buildDecomp(int i){
dfs(i, i);
int r = findCent(i, i, i);
dist[r] = 0;
cur.clear();
dat(r, r);
sort(cur.begin(), cur.end());
ord.clear();
for (int v: cur){
lint vD = dist[v];
while (!ord.empty() && ord.back()[0] >= vD){
int j = ord.back()[1];
ind ++;
lint d = ord.back()[0] + vD;
//events.push_back({j, d, ind});
//events.push_back({v, d, ind});
events[ind2++] = {j, d, ind};
events[ind2++] = {v, d, ind};
ord.pop_back();
}
ord.push_back({vD, v});
}
ord.clear();
for (int x = cur.size()-1; x >= 0; x --){
int v = cur[x];
lint vD = dist[v];
while (!ord.empty() && ord.back()[0] >= vD){
int j = ord.back()[1];
ind ++;
lint d = ord.back()[0] + vD;
//events.push_back({j, d, ind});
//events.push_back({v, d, ind});
events[ind2++] = {j, d, ind};
events[ind2++] = {v, d, ind};
ord.pop_back();
}
ord.push_back({vD, v});
}
for (array<lint, 2> e: ::con[r]){
::con[e[0]].erase({r, e[1]});
buildDecomp(e[0]);
}
}
void decomp(){
buildDecomp(0);
//BigThing b;
//b.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});
}
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;
}
*/
decomp::decomp();
sort(decomp::events, decomp::events + decomp::ind2);
//sort(decomp::events.begin(), decomp::events.end());
if (n == 199999) exit(0);
/*
for (array<lint, 3> p : decomp::events){
cout << p[0] << " " << p[1] << " " << p[2] << endl;
}
*/
}
int main(){
cout << "START" << endl;
prep();
int l = -1;
int r = -1;
set<array<lint, 2>> rans;
lint val = 1e18;
using namespace decomp;
auto beg = events, end = events+ind2;
//auto beg = events.begin(), end = events.end();
decltype(beg) 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 = events.lower_bound((array<lint, 2>){r, -1, -1});
at = lower_bound(beg, end, (array<lint, 3>){r, -1, -1});
}
//ans[k] = val;
ans[k] = 1e18;
set<array<lint, 2>> back;
if (queries[x][1] < r){
for (auto it = lower_bound(beg, end, (array<lint, 3>){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 != end && (*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 = lower_bound(beg, end, (array<lint, 3>){queries[x][0], -1, -1}); (*it)[0] < r; ++ it){
if (rans.find((array<lint, 2>){(*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
Wrong Answer
time: 0ms
memory: 18712kb
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
output:
START -1 3 7 7 2
result:
wrong output format Expected integer, but "START" found