QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#563521 | #5148. Tree Distance | synonym | ML | 0ms | 0kb | C++17 | 3.7kb | 2024-09-14 13:27:48 | 2024-09-14 13:27:49 |
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];
vector<array<int,2>> dist[mxn];
int dfs_size(int v, int p) {
if (vis[v]) return 0;
int su = 1;
for (auto [u,d] : adj[v]) {
if (u==p) continue;
su += dfs_size(u,v);
}
return su;
}
int dfs_dist(int v, int p, int dt, int o) {
if (vis[v]) return 0;
dist[o].push_back({v,dt});
for (auto [u,d] : adj[v]) {
if (u==p) continue;
dfs_dist(u,v,dt+d,o);
}
}
int centroid(int v, int p, int sub) {
//check if v is valid
int ok = 1;
for (auto [u,d] : adj[v]) {
if (dfs_size(u,v)*2 > sub) {
ok=0;
break;
}
}
if (!ok) {
for (auto [u,d] : adj[v]) {
if (u==p) continue;
if (vis[u]) continue;
if (centroid(u,v,sub)) return 1;
}
assert(0);
return 0;
} else {
dfs_dist(v,v,0,v);
vis[v] = 1;
for (auto [u,d] : adj[v]) {
if (vis[u]) continue;
int k = dfs_size(u,u);
centroid(u,u,k);
}
return 1;
}
}
struct RMQ {
int INF = 1e16;
int len = 1;
vector<int> segmx;
RMQ() {}
RMQ(int l) {
while (len < l) len *= 2;
segmx = vector<int>(2*len,INF);
}
RMQ(vector<int> arr) {
while (len < sz(arr)) len *= 2;
segmx = vector<int>(2*len,INF);
for (int i = 0; i < sz(arr); i++) {segmx[len+i] = arr[i];}
for (int i = len-1; i > 0; i--) {
segmx[i] = min(segmx[2*i], segmx[2*i+1]);
}
}
void set(int ind, int val) {
assert(0 <= ind && ind < len);
ind += len; segmx[ind] = val;
while (ind /= 2) {segmx[ind] = min(segmx[2*ind], segmx[2*ind+1]);}
}
int rangemin(int l, int r) {
int res = INF; r++;
for (l += len, r += len; l < r; l /= 2, r /= 2) {
if (l&1) res = min(res, segmx[l++]);
if (r&1) res = min(res, segmx[--r]);
}
return res;
}
};
vector<array<int,3>> rg;
int q;
array<int,3> qry[1000001];
RMQ 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});
}
centroid(0,0,n);
for (int X=0; X<n; X++) {
sort(all(dist[X]));
// cout<<X<<":\n";
// for (auto [a,b] : dist[X]) cout<<a<<","<<b<<" ";
// cout<<endl;
stack<array<int,2>> mono;
//forward
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]});
// if (i<mono.top()[0]) cout<<i<<endl;
}
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]});
// if (i>mono.top()[0]) cout<<i<<endl;
}
mono.push(dist[X][i]);
}
}
rr = RMQ(n);
sort(all(rg)); reverse(all(rg));
int q; 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;
}
// for (auto [a,b,c] : rg) {
// cout<<a+1<<" "<<b+1<<" "<<c<<endl;
// }
// return 0;
sort(qry,qry+q);
reverse(qry,qry+q);
int rp = 0, qp = 0;
for (int i=n-1; i>=0; i--) {
while (rp < sz(rg) && rg[rp][0]==i) {
int pp = rg[rp][1];
int vv = rr.rangemin(pp,pp);
rr.set(pp,min(vv,rg[rp][2]));
rp++;
}
while (qp < q && qry[qp][0]==i) {
ans[qry[qp][2]] = rr.rangemin(i,qry[qp][1]);
qp++;
}
}
for (int i=0; i<q; i++) {
cout<<(ans[i]>1e15?-1:ans[i])<<"\n";
}
return 0;
}
详细
Test #1:
score: 0
Memory 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