oj.uz

Submission #1082000

# Submission time Handle Problem Language Result Execution time Memory
1082000 2024-08-30T14:10:23 Z phong Designated Cities (JOI19_designated_cities) C++17
7 / 100
 958 ms 96084 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;

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];
        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;
        sum -= mp[u][v];
        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];
void dfs(int u, int p){
    dcu[u] = u;
    for(auto v : adj[u]){
        if(v == p) continue;
        rev[v] = rev[u] + mp[v][u];
        dfs(v, u);
        h[u] = max(h[v] + mp[v][u], h[u]);
        int x = dcu[v];
        int y = dcu[u];
        if(g[x] + rev[x] > g[y] + rev[y]) dcu[u] = x;
    }
    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] = v;
        else{
            int x = pre[i];
            if(h[x] + mp[x][u] < h[v] + mp[v][u]) pre[i] = 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] = v;
        else{
            int x = suf[i];
            if(h[x] + mp[x][u] < h[v] + mp[v][u]) suf[i] = 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] + rev[x] - rev[u] + h[y] + mp[y][u];
            if(cost > ma){
                ma = cost;
                S = x;
                T = y;
            }
        }
        y = suf[i + 1];
        if(y > 0){
            int cost = g[x] + rev[x] - rev[u] + h[y] + mp[y][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 = leaf[0];
    dfs(1, -1);

    dfs_3(S, -1);
    dfs_4(S, -1);
    sort(dp + 1, dp + 1 + nchain, greater<ll>());
    for(int i = 2; i <= n; ++i){
        sum -= dp[i - 1];
        ans[i] = min(ans[i - 1], sum);
    }
    cin >> q;
    while(q--){
        int x;
        cin >> x;
        cout << ans[x] << endl;
    }


}
/*
4
1 2 1 2
1 3 3 4
1 4 5 6
2 1 2
*/

Compilation message

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 6 ms 14424 KB Output is correct
3 Correct 6 ms 14564 KB Output is correct
4 Correct 10 ms 14564 KB Output is correct
5 Incorrect 7 ms 14424 KB Output isn't correct
6 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 523 ms 71892 KB Output is correct
3 Correct 558 ms 92308 KB Output is correct
4 Correct 492 ms 70536 KB Output is correct
5 Correct 598 ms 72616 KB Output is correct
6 Correct 555 ms 75024 KB Output is correct
7 Correct 697 ms 74308 KB Output is correct
8 Correct 515 ms 93272 KB Output is correct
9 Correct 958 ms 75840 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14428 KB Output is correct
2 Correct 442 ms 71860 KB Output is correct
3 Correct 540 ms 96084 KB Output is correct
4 Correct 489 ms 70352 KB Output is correct
5 Correct 558 ms 72512 KB Output is correct
6 Correct 548 ms 75308 KB Output is correct
7 Incorrect 929 ms 76712 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 6 ms 14424 KB Output is correct
3 Correct 6 ms 14564 KB Output is correct
4 Correct 10 ms 14564 KB Output is correct
5 Incorrect 7 ms 14424 KB Output isn't correct
6 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 523 ms 71892 KB Output is correct
3 Correct 558 ms 92308 KB Output is correct
4 Correct 492 ms 70536 KB Output is correct
5 Correct 598 ms 72616 KB Output is correct
6 Correct 555 ms 75024 KB Output is correct
7 Correct 697 ms 74308 KB Output is correct
8 Correct 515 ms 93272 KB Output is correct
9 Correct 958 ms 75840 KB Output is correct
10 Correct 7 ms 14428 KB Output is correct
11 Correct 442 ms 71860 KB Output is correct
12 Correct 540 ms 96084 KB Output is correct
13 Correct 489 ms 70352 KB Output is correct
14 Correct 558 ms 72512 KB Output is correct
15 Correct 548 ms 75308 KB Output is correct
16 Incorrect 929 ms 76712 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 6 ms 14424 KB Output is correct
3 Correct 6 ms 14564 KB Output is correct
4 Correct 10 ms 14564 KB Output is correct
5 Incorrect 7 ms 14424 KB Output isn't correct
6 Halted 0 ms 0 KB -