oj.uz

Submission #1082059

# Submission time Handle Problem Language Result Execution time Memory
1082059 2024-08-30T16:10:25 Z phong Designated Cities (JOI19_designated_cities) C++17
16 / 100
 816 ms 99156 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];
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;
        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, rev[nmax], 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];
            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];
            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 f[a] + g[a] > f[b] + g[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);
    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:166:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  166 | main(){
      | ^~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14428 KB Output is correct
2 Incorrect 6 ms 14428 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 6 ms 14428 KB Output is correct
2 Correct 453 ms 72204 KB Output is correct
3 Correct 506 ms 92244 KB Output is correct
4 Correct 420 ms 71252 KB Output is correct
5 Correct 600 ms 72516 KB Output is correct
6 Correct 477 ms 75036 KB Output is correct
7 Correct 686 ms 74568 KB Output is correct
8 Correct 485 ms 93264 KB Output is correct
9 Correct 816 ms 77944 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 437 ms 74940 KB Output is correct
3 Correct 534 ms 99156 KB Output is correct
4 Correct 439 ms 73564 KB Output is correct
5 Correct 470 ms 75700 KB Output is correct
6 Correct 482 ms 78540 KB Output is correct
7 Correct 781 ms 79676 KB Output is correct
8 Correct 491 ms 88796 KB Output is correct
9 Correct 788 ms 78592 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14428 KB Output is correct
2 Incorrect 6 ms 14428 KB Output isn't correct
3 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 453 ms 72204 KB Output is correct
3 Correct 506 ms 92244 KB Output is correct
4 Correct 420 ms 71252 KB Output is correct
5 Correct 600 ms 72516 KB Output is correct
6 Correct 477 ms 75036 KB Output is correct
7 Correct 686 ms 74568 KB Output is correct
8 Correct 485 ms 93264 KB Output is correct
9 Correct 816 ms 77944 KB Output is correct
10 Correct 7 ms 14424 KB Output is correct
11 Correct 437 ms 74940 KB Output is correct
12 Correct 534 ms 99156 KB Output is correct
13 Correct 439 ms 73564 KB Output is correct
14 Correct 470 ms 75700 KB Output is correct
15 Correct 482 ms 78540 KB Output is correct
16 Correct 781 ms 79676 KB Output is correct
17 Correct 491 ms 88796 KB Output is correct
18 Correct 788 ms 78592 KB Output is correct
19 Correct 8 ms 14424 KB Output is correct
20 Incorrect 484 ms 75280 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14428 KB Output is correct
2 Incorrect 6 ms 14428 KB Output isn't correct
3 Halted 0 ms 0 KB -