QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#596771#5148. Tree Distancelouhao088#Compile Error//Rust3.7kb2024-09-28 16:25:062024-09-28 16:25:07

Judging History

你现在查看的是最新测评结果

  • [2024-09-28 16:25:07]
  • 评测
  • [2024-09-28 16:25:06]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pr;
typedef long long ll;

const int MAXN=2e5,MAXQ=1e6,LOGN=20,SIZE=2*MAXN*LOGN;
const ll INF=1e18;

inline int Read()
{
    int res;char c;
    while(1) {c=getchar();if('0'<=c && c<='9') {res=c-'0';break;}}
    while(1) {c=getchar();if('0'<=c && c<='9') res=res*10+c-'0';else break;}
    return res;
}

int n,q,QL[MAXQ+5],QR[MAXQ+5];
vector<pr> Tree[MAXN+5];
int Size[MAXN+5];
int CL[SIZE+5],CR[SIZE+5],val[SIZE+5],tot;
int A[MAXQ+5],B[SIZE+5];
ll ans[MAXQ+5];

inline bool cmp0(int a,int b) {return QR[a]<QR[b];}
inline bool cmp1(int a,int b) {return CR[a]<CR[b];}

bool V[MAXN+5];
void CalSize(int now,int fa)
{
    Size[now]=1;
    for(int i=0,rear;i<Tree[now].size();i++)
    {
        rear=Tree[now][i].first;
        if(rear==fa || V[rear]) continue;
        CalSize(rear,now);
        Size[now]+=Size[rear];
    }
}
int FindGC(int now,int fa,int ALL)
{
    bool OK=1;
    for(int i=0,rear;i<Tree[now].size();i++)
    {
        rear=Tree[now][i].first;
        if(rear==fa || V[rear]) continue;
        if(2*Size[rear]>ALL) {OK=0;break;}
    }
    if(2*Size[now]>=ALL && OK) return now;
    for(int i=0,rear,res;i<Tree[now].size();i++)
    {
        rear=Tree[now][i].first;
        if(rear==fa || V[rear]) continue;
        res=FindGC(rear,now,ALL);
        if(res) return res;
    }
    return 0;
}
int Q[MAXN+5],Tail;ll dis[MAXN+5];
void CalMsg(int now,int fa)
{
    Q[++Tail]=now;
    for(int i=0,rear;i<Tree[now].size();i++)
    {
        rear=Tree[now][i].first;
        if(rear==fa || V[rear]) continue;
        dis[rear]=dis[now]+Tree[now][i].second;
        CalMsg(rear,now);
    }
}

int stk[MAXN+5],tp;
void Solve(int now)
{
    CalSize(now,0),now=FindGC(now,0,Size[now]);
    Tail=dis[now]=0,CalMsg(now,0);
    sort(Q+1,Q+Tail+1);
    for(int i=1;i<=Tail;i++)
    {
        while(tp)
            if(dis[Q[i]]>=dis[stk[tp]]) {if(tp>1) ++tot,CL[tot]=stk[tp-1],CR[tot]=stk[tp],val[tot]=dis[stk[tp]]+dis[stk[tp-1]];--tp;}
            else break;
        stk[++tp]=Q[i];
    }
    while(tp) {if(tp>1) ++tot,CL[tot]=stk[tp-1],CR[tot]=stk[tp],val[tot]=dis[stk[tp]]+dis[stk[tp-1]];--tp;}
    for(int i=Tail;i;i--)
    {
        while(tp)
            if(dis[Q[i]]>=dis[stk[tp]]) {if(tp>1) ++tot,CL[tot]=stk[tp],CR[tot]=stk[tp-1],val[tot]=dis[stk[tp]]+dis[stk[tp-1]];--tp;}
            else break;
        stk[++tp]=Q[i];
    }
    while(tp) {if(tp>1) ++tot,CL[tot]=stk[tp],CR[tot]=stk[tp-1],val[tot]=dis[stk[tp]]+dis[stk[tp-1]];--tp;}
    V[now]=1;
    for(int i=0,rear;i<Tree[now].size();i++)
    {
        rear=Tree[now][i].first;
        if(V[rear]) continue;
        Solve(rear);
    }
}

ll minn[MAXN+5];
inline void Init() {for(int i=1;i<=n;i++) minn[i]=INF;}
inline int lowbit(int x) {return x&-x;}
inline void Modify(int x,ll v) {for(;x;x-=lowbit(x)) minn[x]=min(minn[x],v);}
inline ll GetMin(int x) {ll res=INF;for(;x<=n;x+=lowbit(x)) res=min(res,minn[x]);return res;} 

int main()
{
    n=Read();
    for(int i=1,a,b,c;i<n;i++)
    {
        a=Read(),b=Read(),c=Read();
        Tree[a].push_back(make_pair(b,c));
        Tree[b].push_back(make_pair(a,c));
    }
    q=Read();
    for(int i=1;i<=q;i++) QL[i]=Read(),QR[i]=Read();
    Solve(1);
    for(int i=1;i<=q;i++) A[i]=i;
    for(int i=1;i<=tot;i++) B[i]=i;
    sort(A+1,A+q+1,cmp0),sort(B+1,B+tot+1,cmp1);
    Init();
    for(int i=1,j=1;i<=q;i++)
    {
        while(j<=tot && CR[B[j]]<=QR[A[i]]) Modify(CL[B[j]],val[B[j]]),++j;
        ans[A[i]]=GetMin(QL[A[i]]);
    }
    for(int i=1;i<=q;i++)
        if(ans[i]<INF) printf("%lld\n",ans[i]);
        else printf("-1\n");
    return 0;
}

Details

error: expected one of `!` or `[`, found `include`
 --> answer.code:1:2
  |
1 | #include<bits/stdc++.h>
  |  ^^^^^^^ expected one of `!` or `[`

error: aborting due to previous error