oj.uz

Submission #376800

# Submission time Handle Problem Language Result Execution time Memory
376800 2021-03-12T04:13:33 Z jass921026 Designated Cities (JOI19_designated_cities) C++14
16 / 100
 423 ms 44268 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<ll,ll> pii;
#define F first
#define S second
const int MAXN=2E5+10;
vector<pii> G[MAXN];
ll sum[MAXN], sum2[MAXN], path[MAXN], nxt[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;
}
void getNewPath(int x, int f){
    for(auto i:G[x]){
        if(i.F!=f){
            getNewPath(i.F,x);
            ll cp=path[i.F]+i.S;
            if(cp>path[x]){
                path[x]=cp;
                nxt[x]=i.F;
            }
        }
    }
}
priority_queue<ll> pq;
void getPQ(int x, int f, int t, ll s){
    if(x==t) pq.push(s+path[x]);
    for(auto i:G[x]){
        if(i.F==nxt[x]){
            getPQ(i.F,x,t,i.S);
        }
        else if(i.F!=f){
            getPQ(i.F,x,i.F,i.S);
        }
    }
}
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]);
    int newroot=0;
    for(int i=1;i<=n;i++){
        ans[1]=max(ans[1],sum[i]);
        if(sum2[i]>ans[2]){
            ans[2]=sum2[i];
            newroot=i;
        }
    }
    for(int i=1;i<=n;i++) path[i]=0;
    //cout<<"nr "<<newroot<<"\n";
    getNewPath(newroot,0);
    getPQ(newroot,0,newroot,0);
    for(int i=1;i<=n;i++){
        if(!pq.empty()){
            //cout<<pq.top()<<"\n";
            if(i>2) ans[i]=ans[i-1]+pq.top();
            pq.pop();
        } else{
            if(i>2) ans[i]=all;
        }
    }
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        int e;
        cin>>e;
        cout<<all-ans[e]<<"\n";
    }
    return 0;
}
/*
6
1 6 6 12
6 2 5 16
1 4 13 4
5 1 19 3
3 1 9 13
3
1
2
3
*/
/*
7
2 4 9 9
2 3 8 8
1 4 4 4
4 5 10 10
1 6 3 3
1 7 5 4
5
1 2 3 4 5
*/

Subtask #1
0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 356 ms 24128 KB Output is correct
3 Correct 423 ms 41324 KB Output is correct
4 Correct 346 ms 24340 KB Output is correct
5 Correct 343 ms 24036 KB Output is correct
6 Correct 364 ms 26720 KB Output is correct
7 Correct 291 ms 24668 KB Output is correct
8 Correct 393 ms 42092 KB Output is correct
9 Correct 227 ms 24736 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 343 ms 24036 KB Output is correct
3 Correct 395 ms 44268 KB Output is correct
4 Correct 337 ms 24036 KB Output is correct
5 Correct 328 ms 24160 KB Output is correct
6 Correct 359 ms 27108 KB Output is correct
7 Correct 232 ms 26068 KB Output is correct
8 Correct 383 ms 35556 KB Output is correct
9 Correct 214 ms 24532 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 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Incorrect 4 ms 5100 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 356 ms 24128 KB Output is correct
3 Correct 423 ms 41324 KB Output is correct
4 Correct 346 ms 24340 KB Output is correct
5 Correct 343 ms 24036 KB Output is correct
6 Correct 364 ms 26720 KB Output is correct
7 Correct 291 ms 24668 KB Output is correct
8 Correct 393 ms 42092 KB Output is correct
9 Correct 227 ms 24736 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct
11 Correct 343 ms 24036 KB Output is correct
12 Correct 395 ms 44268 KB Output is correct
13 Correct 337 ms 24036 KB Output is correct
14 Correct 328 ms 24160 KB Output is correct
15 Correct 359 ms 27108 KB Output is correct
16 Correct 232 ms 26068 KB Output is correct
17 Correct 383 ms 35556 KB Output is correct
18 Correct 214 ms 24532 KB Output is correct
19 Correct 4 ms 5100 KB Output is correct
20 Incorrect 352 ms 24164 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 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Incorrect 4 ms 5100 KB Output isn't correct
5 Halted 0 ms 0 KB -