QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#564633 | #5148. Tree Distance | fryan | WA | 0ms | 17416kb | C++17 | 3.3kb | 2024-09-15 11:51:58 | 2024-09-15 11:51:58 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
const int mxn = 2e5+5;
int n;
vector<array<int,2>> adj[mxn];
//centroid
int vis[mxn], sub[mxn];
vector<array<int,2>> dist[mxn];
void dfs_dist(int v, int p, int dt, int o) {
if (vis[v]) return;
dist[o].push_back({v,dt});
for (auto [u,d] : adj[v]) {
if (u==p) continue;
dfs_dist(u,v,dt+d,o);
}
}
int dfs_sub(int v, int p) {
if (vis[v]) return 0;
sub[v] = 1;
for (auto [u,d] : adj[v]) {
if (u==p) continue;
sub[v] += dfs_sub(u, v);
}
return sub[v];
}
int centroid(int v, int p, int sz) {
for (auto [u,d] : adj[v]) {
if (vis[u] || u==p) continue;
if (sub[u]*2 > sz) return centroid(u, v, sz);
}
return v;
}
void build_centroid(int v) {
int c = centroid(v,v,dfs_sub(v,v));
dfs_dist(c, c, 0, c);
vis[c] = 1;
for (auto [u,d] : adj[c]) {
if (vis[u]) continue;
build_centroid(u);
}
}
struct Tree {
typedef int T;
static constexpr T unit = 1e9;
T f(T a, T b) { return min(a, b); } // (any associative fn)
vector<T> s; int n;
Tree(int n = 0, T def = unit) : s(2*n, def), n(n) {}
void update(int pos, T val) {
for (s[pos += n] = val; pos /= 2;)
s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
}
T query(int b, int e) { // query [b, e)
T ra = unit, rb = unit;
for (b += n, e += n; b < e; b /= 2, e /= 2) {
if (b % 2) ra = f(ra, s[b++]);
if (e % 2) rb = f(s[--e], rb);
}
return f(ra, rb);
}
};
vector<array<int,3>> rg;
int q;
array<int,3> qry[5*mxn];
Tree rr;
int ans[mxn];
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin>>n;
for (int i=1; i<n; i++) {
int u,v,w; cin>>u>>v>>w; --u; --v;
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
build_centroid(0);
for (int X=0; X<n; X++) {
sort(all(dist[X]));
stack<array<int,2>> mono;
for (int i=0; i<sz(dist[X]); i++) {
while (sz(mono) && mono.top()[1] > dist[X][i][1]) {mono.pop();}
if (sz(mono)) {
rg.push_back({mono.top()[0],dist[X][i][0],mono.top()[1]+dist[X][i][1]});
}
mono.push(dist[X][i]);
}
while (sz(mono)) mono.pop();
for (int i=sz(dist[X])-1; i>=0; i--) {
while (sz(mono) && mono.top()[1] > dist[X][i][1]) {mono.pop();}
if (sz(mono)) {
rg.push_back({dist[X][i][0],mono.top()[0],mono.top()[1]+dist[X][i][1]});
}
mono.push(dist[X][i]);
}
}
rr = Tree(n+5);
sort(all(rg)); reverse(all(rg));
cin>>q;
for (int i=0; i<q; i++) {
cin>>qry[i][0]>>qry[i][1]; --qry[i][0], --qry[i][1];
qry[i][2] = i;
}
sort(qry,qry+q);
reverse(qry,qry+q);
int rp = 0, qp = 0;
if (n>10) cout<<q<<endl;
for (int i=n-1; i>=0; i--) {
while (rp < sz(rg) && rg[rp][0]==i) {
int pp = rg[rp][1];
int vv;
vv = rr.query(pp,pp+1);
rr.update(pp,min(vv,rg[rp][2]));
rp++;
}
while (qp < q && qry[qp][0]==i) {
ans[qry[qp][2]] = rr.query(i,qry[qp][1]+1);
qp++;
}
if (qp < q && qry[qp][0]>n) {
cout<<qry[qp][0]<<" "<<qry[qp][2]<<endl;
cout<<qp<<endl;
cout<<qry[qp+1][0]<<" "<<qry[qp+1][2]<<endl;
}
}
if (qp != q) {
cout<<qp<<"\n";
cout<<qry[qp][0]<<" "<<qry[qp][1]<<endl;
return 0;
}
for (int i=0; i<q; i++) {
cout<<(ans[i]>1e15?-1:ans[i])<<"\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 17416kb
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:
1000000000 3 7 7 2
result:
wrong answer 1st numbers differ - expected: '-1', found: '1000000000'