oj.uz

Submission #1082064

# Submission time Handle Problem Language Result Execution time Memory
1082064 2024-08-30T16:27:17 Z phong Designated Cities (JOI19_designated_cities) C++17
22 / 100
 839 ms 99596 KB 
#include<bits/stdc++.h>

#define ll long long
#define int long long
const int nmax = 2e5 + 5, N = 1e5;
const ll oo = 1e18 + 1, base = 311;
const int lg = 19, M = 10;
const ll mod = 998244353, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int n, q;
map<int, int> mp[nmax];
ll f[nmax], rev[nmax];
vector<int> adj[nmax], leaf;
int par[nmax];
void dfs_1(int u, int p){
    bool ok = 1;
    for(auto v : adj[u]){
        if(v == p) continue;
        rev[v] = rev[u] + mp[u][v];
        dfs_1(v, u);
        f[u] += f[v] + mp[u][v];
        par[v] = u;
        ok = 0;
    }
    if(ok) leaf.push_back(u);
}
ll pre[nmax], suf[nmax], g[nmax];
struct node{
    int u,v, x, y;
}a[nmax];
void dfs_2(int u, int p){
    int k = adj[u].size();
    pre[0] = suf[k + 1] = 0;
    for(int i = 1; i <= k; ++i){
        int v = adj[u][i -1];
        pre[i] = pre[i - 1];
        if(v == p) continue;
        pre[i] += mp[u][v] + f[v];
    }
    for(int i = k; i >= 1; --i){
        int v = adj[u][i - 1];
        suf[i] = suf[i + 1];
        if(v == p) continue;
        suf[i] += mp[u][v] + f[v];
    }
    for(int i = 1; i <= k; ++i){
        int v = adj[u][i - 1];
        if(v == p) continue;
        g[v] = g[u] + mp[v][u] + pre[i - 1] + suf[i + 1];
    }
    for(auto v: adj[u]){
        if(v == p) continue;
        dfs_2(v, u);
    }
}
ll sum = 0;
int h[nmax], one[nmax];
ll dp[nmax], nchain = 1;

void dfs_3(int u, int p){
    h[u] = 0;
    for(auto v : adj[u]){
        if(v == p) continue;
        dfs_3(v, u);
        h[u] = max(h[v] + mp[v][u], h[u]);
    }
}
void dfs_4(int u, int p){
    for(auto v : adj[u]){
        one[v] = h[v] + mp[v][u];
    }
    sort(adj[u].begin(), adj[u].end(), [](int a, int b){
         return one[a] > one[b];
         });
    int idx = -1;
    for(auto v : adj[u]){
        if(v == p) continue;
        idx = v;
        break;
    }
    if(idx != -1){
        dp[nchain] += mp[idx][u];
        dfs_4(idx, u);
    }
    for(auto v : adj[u]){
        if(v == p || idx == v) continue;
        ++nchain;
        dp[nchain] += mp[v][u];
        dfs_4(v, u);
    }
}
ll S, T, dcu[nmax], ma = -oo, two[nmax];
void dfs(int u, int p){
    dcu[u] = h[u] = u;
    for(auto v : adj[u]){
        if(v == p) continue;
        rev[v] = rev[u] + mp[v][u];
        two[v] = two[u] + mp[u][v];
        dfs(v, u);

        int x = dcu[v];
        int y = dcu[u];
        if(g[x] + rev[x] > g[y] + rev[y]) dcu[u] = x;
        x = h[u];
        y = h[v];
        if(rev[x] < rev[y]) h[u] = y;
    }
    for(auto v : adj[u]){
        if(v == p) continue;
//        cout << dcu[v] << ' ';
    }
    int k = adj[u].size();
    pre[0] = suf[k + 1] = 0;
    for(int i = 1; i <= k; ++i){
        int v = adj[u][i - 1];
        pre[i] = pre[i - 1];
        if(v == p) continue;
        if(pre[i] == 0) pre[i] = h[v];
        else{
            int x = pre[i];
            if(rev[x] < rev[h[v]]) pre[i] = h[v];
        }
    }

    for(int i = k; i >= 1; --i){
        int v = adj[u][i - 1];
        suf[i] = suf[i + 1];
        if(v == p) continue;
        if(suf[i] == 0) suf[i] = h[v];
        else{
            int x = suf[i];
            if(rev[x] < rev[h[v]]) suf[i] = h[v];
        }
    }
    for(int i = 1; i <= k; ++i){
        int v = adj[u][i - 1];
        if(v == p) continue;
        int x = dcu[v];
        int y = pre[i - 1];
        if(y > 0){
            int cost = g[x] + two[x] - two[u] + rev[y] -rev[u];
//        cout << x << ' ' << y << ' ' << cost << endl;
            if(cost > ma){
                ma = cost;
                S = x;
                T = y;
            }
        }
        y = suf[i + 1];
        if(y > 0){
            int cost = g[x] + two[x] - two[u] + rev[y] -rev[u];
//                cout << x << ' ' << y << ' ' << cost << endl;

            if(cost > ma){
                ma = cost;
                S = x;
                T = y;
            }
        }
    }
}
ll ans[nmax];

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n;
     sum = 0;
    for(int i = 1, u, v, x, y; i < n; ++i){
        cin >> u >> v >> x >> y;
        adj[u].push_back(v);
        adj[v].push_back(u);
        mp[u][v] = y;
        mp[v][u] = x;
        sum += x + y;
        a[i] = {u, v, x, y};
    }
    dfs_1(1, -1);
    dfs_2(1, -1);
    ans[1] = oo;
    for(int i = 1; i <= n; ++i){
        ans[1] = min(ans[1], sum - f[i] - g[i]);
    }
    sort(leaf.begin(), leaf.end(), [](int a, int b){
         return  g[a] + rev[a] > g[b] + rev[b];
         });
    S = 1, T = leaf[0], ma = g[T];
    int x = T;
    while(x > 1){
        ma += mp[par[x]][x];
        x = par[x];
    }
    dfs(1, -1);
//    cout << S << ' ' << T <<' ' << ma << endl;
    dfs_3(S, -1);
    dfs_4(S, -1);
    sort(dp + 1, dp + 1 + nchain, greater<ll>());
    ans[2] = sum - ma;
    for(int i = 3; i <= n; ++i){
        ans[i] = ans[i - 1] - dp[i - 1];
    }
    cin >> q;
    while(q--){
        int x;
        cin >> x;
        cout << ans[x] << endl;
    }


}
/*
5
2 4 8 4
3 4 2 2
1 2 7 6
5 4 10 10
1
2

*/

Compilation message

designated_cities.cpp:170:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  170 | main(){
      | ^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 6 ms 14640 KB Output is correct
3 Correct 7 ms 14428 KB Output is correct
4 Correct 9 ms 14504 KB Output is correct
5 Correct 6 ms 14452 KB Output is correct
6 Correct 7 ms 14428 KB Output is correct
7 Correct 7 ms 14428 KB Output is correct
8 Correct 6 ms 14428 KB Output is correct
9 Correct 7 ms 14428 KB Output is correct
10 Correct 7 ms 14428 KB Output is correct
11 Correct 6 ms 14416 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 440 ms 68556 KB Output is correct
3 Correct 468 ms 88968 KB Output is correct
4 Correct 381 ms 68552 KB Output is correct
5 Correct 495 ms 69312 KB Output is correct
6 Correct 451 ms 71620 KB Output is correct
7 Correct 625 ms 70988 KB Output is correct
8 Correct 538 ms 89980 KB Output is correct
9 Correct 839 ms 72432 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 426 ms 68640 KB Output is correct
3 Correct 477 ms 92752 KB Output is correct
4 Correct 403 ms 68500 KB Output is correct
5 Correct 498 ms 69124 KB Output is correct
6 Correct 412 ms 72052 KB Output is correct
7 Correct 765 ms 73276 KB Output is correct
8 Correct 486 ms 82376 KB Output is correct
9 Correct 819 ms 72492 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 6 ms 14640 KB Output is correct
3 Correct 7 ms 14428 KB Output is correct
4 Correct 9 ms 14504 KB Output is correct
5 Correct 6 ms 14452 KB Output is correct
6 Correct 7 ms 14428 KB Output is correct
7 Correct 7 ms 14428 KB Output is correct
8 Correct 6 ms 14428 KB Output is correct
9 Correct 7 ms 14428 KB Output is correct
10 Correct 7 ms 14428 KB Output is correct
11 Correct 6 ms 14416 KB Output is correct
12 Correct 6 ms 14428 KB Output is correct
13 Correct 7 ms 15192 KB Output is correct
14 Correct 9 ms 15192 KB Output is correct
15 Correct 9 ms 15088 KB Output is correct
16 Incorrect 8 ms 15196 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 440 ms 68556 KB Output is correct
3 Correct 468 ms 88968 KB Output is correct
4 Correct 381 ms 68552 KB Output is correct
5 Correct 495 ms 69312 KB Output is correct
6 Correct 451 ms 71620 KB Output is correct
7 Correct 625 ms 70988 KB Output is correct
8 Correct 538 ms 89980 KB Output is correct
9 Correct 839 ms 72432 KB Output is correct
10 Correct 6 ms 14428 KB Output is correct
11 Correct 426 ms 68640 KB Output is correct
12 Correct 477 ms 92752 KB Output is correct
13 Correct 403 ms 68500 KB Output is correct
14 Correct 498 ms 69124 KB Output is correct
15 Correct 412 ms 72052 KB Output is correct
16 Correct 765 ms 73276 KB Output is correct
17 Correct 486 ms 82376 KB Output is correct
18 Correct 819 ms 72492 KB Output is correct
19 Correct 6 ms 14424 KB Output is correct
20 Correct 444 ms 68552 KB Output is correct
21 Correct 463 ms 99596 KB Output is correct
22 Correct 428 ms 73672 KB Output is correct
23 Incorrect 438 ms 74948 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 6 ms 14640 KB Output is correct
3 Correct 7 ms 14428 KB Output is correct
4 Correct 9 ms 14504 KB Output is correct
5 Correct 6 ms 14452 KB Output is correct
6 Correct 7 ms 14428 KB Output is correct
7 Correct 7 ms 14428 KB Output is correct
8 Correct 6 ms 14428 KB Output is correct
9 Correct 7 ms 14428 KB Output is correct
10 Correct 7 ms 14428 KB Output is correct
11 Correct 6 ms 14416 KB Output is correct
12 Correct 6 ms 14428 KB Output is correct
13 Correct 440 ms 68556 KB Output is correct
14 Correct 468 ms 88968 KB Output is correct
15 Correct 381 ms 68552 KB Output is correct
16 Correct 495 ms 69312 KB Output is correct
17 Correct 451 ms 71620 KB Output is correct
18 Correct 625 ms 70988 KB Output is correct
19 Correct 538 ms 89980 KB Output is correct
20 Correct 839 ms 72432 KB Output is correct
21 Correct 6 ms 14428 KB Output is correct
22 Correct 426 ms 68640 KB Output is correct
23 Correct 477 ms 92752 KB Output is correct
24 Correct 403 ms 68500 KB Output is correct
25 Correct 498 ms 69124 KB Output is correct
26 Correct 412 ms 72052 KB Output is correct
27 Correct 765 ms 73276 KB Output is correct
28 Correct 486 ms 82376 KB Output is correct
29 Correct 819 ms 72492 KB Output is correct
30 Correct 6 ms 14428 KB Output is correct
31 Correct 7 ms 15192 KB Output is correct
32 Correct 9 ms 15192 KB Output is correct
33 Correct 9 ms 15088 KB Output is correct
34 Incorrect 8 ms 15196 KB Output isn't correct
35 Halted 0 ms 0 KB -