oj.uz

Submission #376797

# Submission time Handle Problem Language Result Execution time Memory
376797 2021-03-12T04:08:40 Z jass921026 Designated Cities (JOI19_designated_cities) C++14
16 / 100
 394 ms 37612 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], 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 342 ms 21740 KB Output is correct
3 Correct 394 ms 34924 KB Output is correct
4 Correct 329 ms 21476 KB Output is correct
5 Correct 317 ms 21600 KB Output is correct
6 Correct 343 ms 23520 KB Output is correct
7 Correct 274 ms 21860 KB Output is correct
8 Correct 384 ms 35820 KB Output is correct
9 Correct 221 ms 21464 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 362 ms 21516 KB Output is correct
3 Correct 375 ms 37612 KB Output is correct
4 Correct 327 ms 21352 KB Output is correct
5 Correct 340 ms 21600 KB Output is correct
6 Correct 353 ms 23776 KB Output is correct
7 Correct 223 ms 22616 KB Output is correct
8 Correct 365 ms 30572 KB Output is correct
9 Correct 220 ms 21336 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 342 ms 21740 KB Output is correct
3 Correct 394 ms 34924 KB Output is correct
4 Correct 329 ms 21476 KB Output is correct
5 Correct 317 ms 21600 KB Output is correct
6 Correct 343 ms 23520 KB Output is correct
7 Correct 274 ms 21860 KB Output is correct
8 Correct 384 ms 35820 KB Output is correct
9 Correct 221 ms 21464 KB Output is correct
10 Correct 4 ms 5120 KB Output is correct
11 Correct 362 ms 21516 KB Output is correct
12 Correct 375 ms 37612 KB Output is correct
13 Correct 327 ms 21352 KB Output is correct
14 Correct 340 ms 21600 KB Output is correct
15 Correct 353 ms 23776 KB Output is correct
16 Correct 223 ms 22616 KB Output is correct
17 Correct 365 ms 30572 KB Output is correct
18 Correct 220 ms 21336 KB Output is correct
19 Correct 4 ms 5100 KB Output is correct
20 Incorrect 344 ms 21604 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 -