oj.uz

Submission #865129

# Submission time Handle Problem Language Result Execution time Memory
865129 2023-10-24T05:49:08 Z LittleOrange Designated Cities (JOI19_designated_cities) C++17
22 / 100
 259 ms 56040 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct obj{
    ll to,c0,c1;// to, back
};
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n,q;
    cin >> n;
    vector<vector<obj>> con(n);
    ll tot = 0;
    for(ll i = 1;i<n;i++){
        ll a,b,c,d;
        cin >> a >> b >> c >> d;a--;b--;
        con[a].push_back({b,c,d});
        con[b].push_back({a,d,c});
        tot += c+d;
    }
    ll leaf_cnt = 0;
    for(auto &o : con) if (o.size()==1) leaf_cnt++;
    cin >> q;
    bool use16 = true;
    if (n<=16&&use16){
        vector<ll> ans(n+1,tot);
        //vector<ll> ch(n+1,0);
        ll cur = tot;
        vector<vector<ll>> used(n,vector<ll>(n,0));
        function<void(ll,ll)> dfs;
        dfs = [&](ll i, ll p){
            for(obj l : con[i]){
                if (l.to!=p){
                    if (!used[i][l.to]){
                        used[i][l.to] = 1;
                        cur -= l.c1;
                    }
                    dfs(l.to,i);
                }
            }
        };
        for(ll x = 1;x<(1<<n);x++){
            cur = tot;
            for(ll i = 0;i<n;i++) for(ll j = 0;j<n;j++) used[i][j] = 0;
            ll lvl = __builtin_popcountll(x);
            for(ll i = 0;i<n;i++) if(x>>i&1) dfs(i,-1);
            //if (cur<ans[lvl]) ch[lvl] = x;
            ans[lvl] = min(ans[lvl],cur);
        }
        while(q--){
            ll e;
            cin >> e;
            cout << ans[e] << "\n";
            //for(ll i = 0;i<n;i++) cout << (ch[e]>>i&1);
            //cout << "\n";
        }
        return 0;
    }
    vector<ll> dp(n,0);
    {
        function<ll(ll,ll)> dfs;
        dfs = [&](ll i, ll p){
            ll cur = 0;
            for(obj l : con[i]){
                if (l.to!=p){
                    cur += l.c1 + dfs(l.to,i);
                }
            }
            return cur;
        };
        dp[0] = dfs(0,-1);
    }
    {
        function<void(ll,ll,ll)> dfs;
        dfs = [&](ll i, ll p, ll v){
            dp[i] = v;
            for(obj l : con[i]){
                if (l.to!=p){
                    dfs(l.to,i,v+l.c0-l.c1);
                }
            }
        };
        dfs(0,-1,dp[0]);
    }
    ll ans_1 = tot;
    for(ll i : dp) ans_1 = min(tot-i,ans_1);
    ll ans_2 = tot;
    vector<ll> go(n,0),ch(n,0);
    {
        function<void(ll,ll)> dfs;
        dfs = [&](ll i, ll p){
            ll de = 0;
            for(obj l : con[i]){
                if (l.to!=p){
                    dfs(l.to,i);
                    go[i] += go[l.to]+l.c0;
                    de = max(de,go[l.to]+l.c0 - ch[l.to]);
                }
            }
            ch[i] = go[i] - de;
        };
        dfs(0,-1);
    }
    {
        function<void(ll,ll,ll)> dfs;
        dfs = [&](ll i, ll p, ll v){
            ll w = v;
            for(obj l : con[i]){
                if (l.to!=p){
                    w += go[l.to]+l.c0;
                }
            }
            ll a = 0,b = 0;
            for(obj l : con[i]){
                if (l.to!=p){
                    dfs(l.to,i,w-(go[l.to]+l.c0)+l.c1);
                    ll cur = go[l.to]+l.c0 - ch[l.to];
                    if (cur>=a){
                        b = a;
                        a = cur;
                    }else b = max(b,cur);
                }
            }
            ans_2 = min(ans_2, w-a-b);
        };
        dfs(0,-1, 0);
    }
    while(q--){
        ll e;
        cin >> e;
        if (e>=leaf_cnt){
            cout << "0\n";
            continue;
        }
        if (e==1){
            cout << ans_1 << "\n";
            continue;
        }
        if (e==2){
            cout << ans_2 << "\n";
            continue;
        }
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 66 ms 348 KB Output is correct
3 Correct 72 ms 432 KB Output is correct
4 Correct 64 ms 344 KB Output is correct
5 Correct 70 ms 440 KB Output is correct
6 Correct 66 ms 348 KB Output is correct
7 Correct 68 ms 348 KB Output is correct
8 Correct 64 ms 352 KB Output is correct
9 Correct 62 ms 348 KB Output is correct
10 Correct 71 ms 592 KB Output is correct
11 Correct 61 ms 348 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 183 ms 26476 KB Output is correct
3 Correct 259 ms 49492 KB Output is correct
4 Correct 181 ms 25956 KB Output is correct
5 Correct 173 ms 26120 KB Output is correct
6 Correct 200 ms 29844 KB Output is correct
7 Correct 148 ms 25160 KB Output is correct
8 Correct 256 ms 50080 KB Output is correct
9 Correct 89 ms 24368 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 205 ms 26560 KB Output is correct
3 Correct 248 ms 56040 KB Output is correct
4 Correct 164 ms 27772 KB Output is correct
5 Correct 189 ms 29192 KB Output is correct
6 Correct 201 ms 33104 KB Output is correct
7 Correct 104 ms 28228 KB Output is correct
8 Correct 244 ms 44184 KB Output is correct
9 Correct 93 ms 26880 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 66 ms 348 KB Output is correct
3 Correct 72 ms 432 KB Output is correct
4 Correct 64 ms 344 KB Output is correct
5 Correct 70 ms 440 KB Output is correct
6 Correct 66 ms 348 KB Output is correct
7 Correct 68 ms 348 KB Output is correct
8 Correct 64 ms 352 KB Output is correct
9 Correct 62 ms 348 KB Output is correct
10 Correct 71 ms 592 KB Output is correct
11 Correct 61 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Incorrect 2 ms 600 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 183 ms 26476 KB Output is correct
3 Correct 259 ms 49492 KB Output is correct
4 Correct 181 ms 25956 KB Output is correct
5 Correct 173 ms 26120 KB Output is correct
6 Correct 200 ms 29844 KB Output is correct
7 Correct 148 ms 25160 KB Output is correct
8 Correct 256 ms 50080 KB Output is correct
9 Correct 89 ms 24368 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 205 ms 26560 KB Output is correct
12 Correct 248 ms 56040 KB Output is correct
13 Correct 164 ms 27772 KB Output is correct
14 Correct 189 ms 29192 KB Output is correct
15 Correct 201 ms 33104 KB Output is correct
16 Correct 104 ms 28228 KB Output is correct
17 Correct 244 ms 44184 KB Output is correct
18 Correct 93 ms 26880 KB Output is correct
19 Correct 0 ms 604 KB Output is correct
20 Incorrect 190 ms 29216 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 66 ms 348 KB Output is correct
3 Correct 72 ms 432 KB Output is correct
4 Correct 64 ms 344 KB Output is correct
5 Correct 70 ms 440 KB Output is correct
6 Correct 66 ms 348 KB Output is correct
7 Correct 68 ms 348 KB Output is correct
8 Correct 64 ms 352 KB Output is correct
9 Correct 62 ms 348 KB Output is correct
10 Correct 71 ms 592 KB Output is correct
11 Correct 61 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 183 ms 26476 KB Output is correct
14 Correct 259 ms 49492 KB Output is correct
15 Correct 181 ms 25956 KB Output is correct
16 Correct 173 ms 26120 KB Output is correct
17 Correct 200 ms 29844 KB Output is correct
18 Correct 148 ms 25160 KB Output is correct
19 Correct 256 ms 50080 KB Output is correct
20 Correct 89 ms 24368 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 205 ms 26560 KB Output is correct
23 Correct 248 ms 56040 KB Output is correct
24 Correct 164 ms 27772 KB Output is correct
25 Correct 189 ms 29192 KB Output is correct
26 Correct 201 ms 33104 KB Output is correct
27 Correct 104 ms 28228 KB Output is correct
28 Correct 244 ms 44184 KB Output is correct
29 Correct 93 ms 26880 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Incorrect 2 ms 600 KB Output isn't correct
32 Halted 0 ms 0 KB -