oj.uz

Submission #376689

# Submission time Handle Problem Language Result Execution time Memory
376689 2021-03-12T01:51:20 Z jass921026 Designated Cities (JOI19_designated_cities) C++14
7 / 100
 479 ms 23532 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,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.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 4972 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 4 ms 4972 KB Output is correct
2 Correct 455 ms 13936 KB Output is correct
3 Correct 478 ms 23148 KB Output is correct
4 Correct 412 ms 13932 KB Output is correct
5 Correct 435 ms 14184 KB Output is correct
6 Correct 447 ms 15340 KB Output is correct
7 Correct 433 ms 14308 KB Output is correct
8 Correct 479 ms 23532 KB Output is correct
9 Correct 367 ms 14428 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 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 5 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 4 ms 4972 KB Output is correct
2 Correct 455 ms 13936 KB Output is correct
3 Correct 478 ms 23148 KB Output is correct
4 Correct 412 ms 13932 KB Output is correct
5 Correct 435 ms 14184 KB Output is correct
6 Correct 447 ms 15340 KB Output is correct
7 Correct 433 ms 14308 KB Output is correct
8 Correct 479 ms 23532 KB Output is correct
9 Correct 367 ms 14428 KB Output is correct
10 Incorrect 4 ms 4972 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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