Submission #376689

#	Time	Username	Problem	Language	Result	Execution time	Memory
376689		jass921026	Designated Cities (JOI19_designated_cities)	C++14	7 / 100	479 ms	23532 KiB

designated_cities

#include<bits/stdc++.h>
using namespace std;
#define jizz ios_base::sync_with_stdio(false);cin.tie(NULL);
typedef long long ll;
typedef pair<int,int> pii;
#define F first
#define S second
const int MAXN=2E5+10;
vector<pii> G[MAXN];
ll sum[MAXN];
void init(int x, int f){
    for(auto i:G[x]){
        if(i.F!=f){
            init(i.F,x);
        } else{
            sum[1]+=i.S;
        }
    }
}
void getSum(int x, int f, ll s){
    for(auto i:G[x]){
        if(i.F==f){
            sum[x]=s-i.S;
            break;
        }
    }
    for(auto i:G[x]){
        if(i.F!=f){
            getSum(i.F,x,sum[x]+i.S);
        }
    }
}
int main(){
    int n;
    cin>>n;
    ll all=0;
    for(int i=0;i<n-1;i++){
        int a, b, c, d;
        cin>>a>>b>>c>>d;
        G[a].push_back({b,c});
        G[b].push_back({a,d});
        all=all+c+d;
    }
    init(1,0);
    getSum(1,0,sum[1]);
    ll mx=0;
    for(int i=1;i<=n;i++){
        //cout<<sum[i]<<" ";
        mx=max(mx,sum[i]);
    }
    cout<<"\n";
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        int e;
        cin>>e;
        if(e==1) cout<<all-mx<<"\n";
    }
    return 0;
}
/*
5
1 3 13 6
5 1 17 8
5 2 6 10
1 4 16 11
1
1
*/

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