QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#355557 | #5102. Dungeon Crawler | InfinityNS# | WA | 1ms | 3920kb | C++14 | 3.1kb | 2024-03-16 20:26:52 | 2024-03-16 20:26:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define f first
#define s second
const int N=2e3+5,L=11;
vector<vector<pair<int,int>>> graf(N);
int up[N][L],dep[N];
ll wdep[N];
void dfs(int tr,int par){
up[tr][0]=par;
for(auto p:graf[tr]){
if(p.f!=par){
dep[p.f]=dep[tr]+1;
wdep[p.f]=wdep[tr]+p.s;
dfs(p.f,tr);
}
}
}
int g(int x,int k){
for(int j=L-1;j>=0;j--){
if((1<<j)<=k){
k-=(1<<j);
x=up[x][j];
}
}
return x;
}
int lc(int a,int b){
if(dep[a]<dep[b])swap(a,b);
a=g(a,dep[a]-dep[b]);
if(a==b)return a;
for(int j=L-1;j>=0;j--){
if(up[a][j]!=up[b][j]){
a=up[a][j];
b=up[b][j];
}
}
return up[a][0];
}
ll aa[N];
ll subT[N];
void dfs3(int tr,int par){
subT[tr]=wdep[tr];
for(auto p:graf[tr]){
if(p.f!=par){
dfs3(p.f,tr);
subT[tr]=max(subT[tr],subT[p.f]);
}
}
}
void dfs2(int tr,int par,ll a){
aa[tr]=a;
vector<int> deca;
for(auto p:graf[tr]){
if(p.f!=par){
deca.pb(p.f);
}
}
vector<ll> ww;
for(auto p:deca){
ww.pb(subT[p]);
}
ll trW=-1;
for(int i=((int)ww.size())-2;i>=0;i--){
ww[i]=max(ww[i],ww[i+1]);
}
for(int i=0;i<ww.size();i++){
ll x=-1;
if(i!=((int)ww.size())-1){
x=ww[i+1];
}
x=max(x,trW);
dfs2(deca[i],tr,x);
trW=max(trW,ww[i]);
}
}
const int Q=2e5+5;
ll ans[Q];
vector<pair<pair<int,int>,int>> qu[N];
int main(){
int n,q;
scanf("%i %i",&n,&q);
ll w2=0;
for(int i=1;i<n;i++){
int u,v,w;
scanf("%i %i %i",&u,&v,&w);
w2+=w;
w2+=w;
u--;v--;
graf[u].pb({v,w});
graf[v].pb({u,w});
}
for(int i=0;i<q;i++){
int s,k,t;
scanf("%i %i %i",&s,&k,&t);
s--;t--;k--;
qu[s].pb({{k,t},i});
}
for(int i=0;i<n;i++){
dep[i]=0;
wdep[i]=0;
dfs(i,i);
for(int j=1;j<L;j++){
for(int i=0;i<n;i++){
up[i][j]=up[up[i][j-1]][j-1];
}
}
dfs3(i,i);
dfs2(i,i,0);
for(auto p:qu[i]){
int k=p.f.f,t=p.f.s;
int ind=p.s;
if(k==t){
ans[ind]=subT[i];
}
else{
int l=lc(k,t);
if(l==t){
ans[ind]=-1;
}
else{
if(k==l){
ans[ind]=subT[i];
}
else{
int sl=g(k,dep[k]-dep[l]-1);
ans[ind]=aa[sl];
}
}
}
}
}
for(int i=0;i<q;i++){
if(ans[i]==-1){
printf("impossible\n");
}
else{
printf("%lld\n",w2-ans[i]);
}
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3920kb
input:
22 5 1 2 7 2 3 5 3 4 8 3 6 6 3 7 3 2 5 6 5 8 2 8 9 11 2 10 16 1 11 12 11 12 4 11 13 9 1 14 25 14 15 4 15 16 5 15 17 6 15 18 1 15 19 8 14 20 7 20 21 9 20 22 17 1 19 9 1 9 19 1 8 9 1 9 8 2 22 11
output:
293 293 293 impossible 286
result:
wrong answer 1st lines differ - expected: '316', found: '293'