oj.uz

Submission #376770

# Submission time Handle Problem Language Result Execution time Memory
376770 2021-03-12T03:33:02 Z jass921026 Designated Cities (JOI19_designated_cities) C++14
16 / 100
 327 ms 40172 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], sum2[MAXN], path[MAXN], ans[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){
    ll maxpath=0, secpath=0;
    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);
            ll cp=path[i.F]+i.S;
            if(cp>maxpath){
                secpath=maxpath;
                maxpath=cp;
            } else{
                secpath=max(secpath,cp);
            }
        }
    }
    path[x]=maxpath;
    sum2[x]=sum[x]+maxpath+secpath;
}
int main(){ jizz
    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]);
    for(int i=1;i<=n;i++){
        ans[1]=max(ans[1],sum[i]);
        ans[2]=max(ans[2],sum2[i]);
    }

    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        int e;
        cin>>e;
        cout<<all-ans[e]<<"\n";
    }
    return 0;
}
/*
4
1 2 1 2
1 3 3 4
1 4 5 6
2
1
2
*/
/*
5
1 3 13 6
5 1 17 8
5 2 6 10
1 4 16 11
1
1
*/
/*
6
1 6 6 12
6 2 5 16
1 4 13 4
5 1 19 3
3 1 9 13
1
2
*/

Subtask #1
0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 260 ms 17132 KB Output is correct
3 Correct 327 ms 31468 KB Output is correct
4 Correct 247 ms 17132 KB Output is correct
5 Correct 245 ms 17124 KB Output is correct
6 Correct 252 ms 19308 KB Output is correct
7 Correct 214 ms 17248 KB Output is correct
8 Correct 284 ms 31852 KB Output is correct
9 Correct 170 ms 17628 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 256 ms 17132 KB Output is correct
3 Correct 292 ms 40172 KB Output is correct
4 Correct 239 ms 21996 KB Output is correct
5 Correct 249 ms 23456 KB Output is correct
6 Correct 293 ms 25984 KB Output is correct
7 Correct 173 ms 23780 KB Output is correct
8 Correct 281 ms 32876 KB Output is correct
9 Correct 164 ms 23644 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 260 ms 17132 KB Output is correct
3 Correct 327 ms 31468 KB Output is correct
4 Correct 247 ms 17132 KB Output is correct
5 Correct 245 ms 17124 KB Output is correct
6 Correct 252 ms 19308 KB Output is correct
7 Correct 214 ms 17248 KB Output is correct
8 Correct 284 ms 31852 KB Output is correct
9 Correct 170 ms 17628 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct
11 Correct 256 ms 17132 KB Output is correct
12 Correct 292 ms 40172 KB Output is correct
13 Correct 239 ms 21996 KB Output is correct
14 Correct 249 ms 23456 KB Output is correct
15 Correct 293 ms 25984 KB Output is correct
16 Correct 173 ms 23780 KB Output is correct
17 Correct 281 ms 32876 KB Output is correct
18 Correct 164 ms 23644 KB Output is correct
19 Correct 4 ms 5100 KB Output is correct
20 Incorrect 260 ms 23404 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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