oj.uz

Submission #376684

# Submission time Handle Problem Language Result Execution time Memory
376684 2021-03-12T01:46:57 Z jass921026 Designated Cities (JOI19_designated_cities) C++14
0 / 100
 452 ms 13932 KB 
#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,s+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++){
        mx=max(mx,sum[i]);
    }
    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.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4972 KB Output is correct
2 Incorrect 452 ms 13932 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4972 KB Output is correct
2 Incorrect 452 ms 13932 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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