Submission #1091940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091940		YassirSalama	Designated Cities (JOI19_designated_cities)	C++17	7 / 100	872 ms	69424 KiB

designated_cities

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define F first
#define S second
const int maxn=2e5+100;
vector<int> v[maxn];
map<pair<int,int>,int> mp;
int dp[maxn];
int a[maxn];
void dfs(int node,int par){
    for(auto x:v[node]){
        if(x==par) continue;
        dfs(x,node);
        dp[node]+=dp[x];
        dp[node]+=mp[{x,node}];
    }
}
void dfs1(int node,int par){
    a[node]=dp[node];
    for(auto x:v[node]){
        if(x==par) continue;
        dp[node]-=dp[x];
        dp[node]-=mp[{x,node}];
        dp[x]+=dp[node];
        dp[x]+=mp[{node,x}];
        dfs1(x,node);
        dp[x]-=dp[node];
        dp[x]-=mp[{node,x}];
        dp[node]+=dp[x];
        dp[node]+=mp[{x,node}];
    }
}
signed main(){
    int n;
    cin>>n;
    int s=0;
    for(int i=1;i<n;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        s+=c;
        s+=d;
        mp[{a,b}]=c;
        mp[{b,a}]=d;
        v[a].pb(b);
        v[b].pb(a);
    }
    dfs(1,1);
    dfs1(1,1);
    int ans=1e18;
    for(int i=1;i<=n;i++) {
        ans=min(ans,s-a[i]); 
    }
    cout<<ans<<endl;
}

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