oj.uz

Submission #1082063

# Submission time Handle Problem Language Result Execution time Memory
1082063 2024-08-30T16:24:18 Z phong Designated Cities (JOI19_designated_cities) C++17
16 / 100
 811 ms 97876 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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Incorrect 6 ms 14612 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 8 ms 14424 KB Output is correct
2 Correct 444 ms 68500 KB Output is correct
3 Correct 454 ms 95316 KB Output is correct
4 Correct 450 ms 73668 KB Output is correct
5 Correct 522 ms 75588 KB Output is correct
6 Correct 443 ms 78068 KB Output is correct
7 Correct 652 ms 77544 KB Output is correct
8 Correct 478 ms 95840 KB Output is correct
9 Correct 754 ms 77880 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14428 KB Output is correct
2 Correct 453 ms 68684 KB Output is correct
3 Correct 444 ms 97876 KB Output is correct
4 Correct 415 ms 72640 KB Output is correct
5 Correct 483 ms 74196 KB Output is correct
6 Correct 445 ms 77340 KB Output is correct
7 Correct 791 ms 78536 KB Output is correct
8 Correct 510 ms 87512 KB Output is correct
9 Correct 811 ms 77504 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 Incorrect 6 ms 14612 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14424 KB Output is correct
2 Correct 444 ms 68500 KB Output is correct
3 Correct 454 ms 95316 KB Output is correct
4 Correct 450 ms 73668 KB Output is correct
5 Correct 522 ms 75588 KB Output is correct
6 Correct 443 ms 78068 KB Output is correct
7 Correct 652 ms 77544 KB Output is correct
8 Correct 478 ms 95840 KB Output is correct
9 Correct 754 ms 77880 KB Output is correct
10 Correct 8 ms 14428 KB Output is correct
11 Correct 453 ms 68684 KB Output is correct
12 Correct 444 ms 97876 KB Output is correct
13 Correct 415 ms 72640 KB Output is correct
14 Correct 483 ms 74196 KB Output is correct
15 Correct 445 ms 77340 KB Output is correct
16 Correct 791 ms 78536 KB Output is correct
17 Correct 510 ms 87512 KB Output is correct
18 Correct 811 ms 77504 KB Output is correct
19 Correct 6 ms 14424 KB Output is correct
20 Incorrect 408 ms 73792 KB Output isn't correct
21 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 Incorrect 6 ms 14612 KB Output isn't correct
3 Halted 0 ms 0 KB -