제출 #1291308

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291308		simona1230	Designated Cities (JOI19_designated_cities)	C++20	0 / 100	2098 ms	59728 KiB

designated_cities

#include <bits/stdc++.h>

using namespace std;
const long long maxn=2*1e5+5;

long long n;
vector<long long> v[maxn],a[maxn],b[maxn];
long long q;
long long e[maxn];
long long sum;

void read()
{
    cin>>n;
    for(long long i=1;i<n;i++)
    {
        long long v1,v2,d1,d2;
        cin>>v1>>v2>>d1>>d2;
        v[v1].push_back(v2);
        v[v2].push_back(v1);
        a[v1].push_back(d1);
        b[v1].push_back(d2);
        a[v2].push_back(d2);
        b[v2].push_back(d1);
        sum+=d1;
        sum+=d2;
    }

    cin>>q;
    for(long long i=1;i<=q;i++)
        cin>>e[i];
}


long long up1[maxn],dw1[maxn];
long long vl[maxn];

void dfs2(long long i,long long p)
{
    for(long long j=0;j<v[i].size();j++)
    {
        long long nb=v[i][j];
        if(nb==p)continue;

        dfs2(nb,i);
        up1[i]+=up1[nb]+b[i][j];
        dw1[i]+=dw1[nb]+a[i][j];
    }
}
long long ans3;

void dfs12(long long i,long long p)
{
    for(long long j=0;j<v[i].size();j++)
    {
        long long nb=v[i][j];
        if(nb==p)continue;
        vl[nb]=vl[i]-b[i][j]+a[i][j];
        ans3=max(ans3,vl[nb]);
        dfs12(nb,i);
    }
}

void solve1()
{
    dfs2(1,0);
    ans3=vl[1]=up1[1];
    dfs12(1,0);
}

long long up,dw[maxn];
long long u[maxn];
long long num,in[maxn],out[maxn];
long long op[maxn];

long long t[4*maxn],td[4*maxn];
long long lz[4*maxn];

void build(long long i,long long l,long long r)
{
    if(l==r)
    {
        t[i]=op[l];
        td[i]=dw[op[l]];
        return;
    }

    long long m=(l+r)/2;
    build(i*2,l,m);
    build(i*2+1,m+1,r);

    if(dw[t[i*2]]>dw[t[i*2+1]])t[i]=t[i*2],td[i]=td[i*2];
    else t[i]=t[i*2+1],td[i]=td[i*2+1];
}

void push(long long i,long long l,long long r)
{
    td[i]+=lz[i];
    if(l!=r)
    {
        lz[i*2]+=lz[i];
        lz[i*2+1]+=lz[i];
    }
    lz[i]=0;
}

void update(long long i,long long l,long long r,long long ql,long long qr,long long vl)
{
    push(i,l,r);
    if(ql>qr)return;
    if(ql<=l&&r<=qr)
    {
        lz[i]+=vl;
        push(i,l,r);
        return;
    }
    long long m=(l+r)/2;
    update(i*2,l,m,ql,min(qr,m),vl);
    update(i*2+1,m+1,r,max(m+1,ql),qr,vl);

    if(td[i*2]>td[i*2+1])t[i]=t[i*2],td[i]=td[i*2];
    else t[i]=t[i*2+1],td[i]=td[i*2+1];
}

// t[i] = the original id of the vertex which is the furthest in l-r

long long par[maxn],val[maxn];
void use(long long i)
{
    if(u[i]||par[i]==0)return;

    //cout<<in[i]<<" "<<out[i]<<" "<<-val[i]<<endl;
    update(1,1,n,in[i],out[i],-val[i]);
    u[i]=1;
    use(par[i]);
}

void dfs(long long i,long long p)
{
    in[i]=num++;
    op[num-1]=i;
    par[i]=p;

    for(long long j=0;j<v[i].size();j++)
    {
        long long nb=v[i][j];
        if(nb==p)continue;
        val[nb]=a[i][j];

        dw[nb]=dw[i]+a[i][j];
        dfs(nb,i);

        up+=b[i][j];
    }
    out[i]=num;
}

long long cnt;
long long ans[2001];
void prec()
{
    for(long long i=1;i<=n;i++)
    {
        if(v[i].size()>=2)continue;
        //cout<<"!! "<<i<<endl;
        cnt++;

        for(int j=1;j<=n;j++)
            u[j]=0;
        num=1;
        up=0;
        dw[i]=0;
        dfs(i,0);

        build(1,1,n);
        long long curs=0;
        ans[0]=max(ans[0],up);

        for(long long j=1;j<=n-1;j++)
        {
            push(1,1,n);
            curs+=td[1];
            //cout<<t[1]<<" "<<td[1]<<endl;
            use(t[1]);
            ans[j]=max(ans[j],up+curs);
        }
    }
}

void solve()
{
    for(long long i=1;i<=q;i++)
    {
        if(e[i]==1)cout<<sum-ans3<<endl;
        else if(e[i]>=cnt)cout<<0<<endl;
        else cout<<sum-ans[e[i]-1]<<endl;
    }
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	read();
	prec();
	solve1();
	solve();
	return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44