oj.uz

Submission #1091940

# Submission time Handle Problem Language Result Execution time Memory
1091940 2024-09-22T16:25:34 Z YassirSalama Designated Cities (JOI19_designated_cities) C++17
7 / 100
 872 ms 69424 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 773 ms 46960 KB Output is correct
3 Correct 872 ms 68692 KB Output is correct
4 Correct 762 ms 45400 KB Output is correct
5 Correct 740 ms 46792 KB Output is correct
6 Correct 768 ms 49944 KB Output is correct
7 Correct 677 ms 47076 KB Output is correct
8 Correct 832 ms 69424 KB Output is correct
9 Correct 622 ms 47612 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 773 ms 46960 KB Output is correct
3 Correct 872 ms 68692 KB Output is correct
4 Correct 762 ms 45400 KB Output is correct
5 Correct 740 ms 46792 KB Output is correct
6 Correct 768 ms 49944 KB Output is correct
7 Correct 677 ms 47076 KB Output is correct
8 Correct 832 ms 69424 KB Output is correct
9 Correct 622 ms 47612 KB Output is correct
10 Incorrect 2 ms 4956 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4952 KB Output isn't correct
2 Halted 0 ms 0 KB -