Submission #1291269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291269		simona1230	Designated Cities (JOI19_designated_cities)	C++20	7 / 100	213 ms	51372 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 up[maxn],dw[maxn];
long long vl[maxn];

void dfs(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;

        dfs(nb,i);
        up[i]+=up[nb]+b[i][j];
        dw[i]+=dw[nb]+a[i][j];
    }
}
long long ans;

void dfs1(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];
        ans=max(ans,vl[nb]);
        dfs1(nb,i);
    }
}

void solve1()
{
    dfs(1,0);
    ans=vl[1]=up[1];
    dfs1(1,0);
    cout<<sum-ans<<endl;
}

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

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