oj.uz

Submission #1115273

# Submission time Handle Problem Language Result Execution time Memory
1115273 2024-11-20T09:43:44 Z hqminhuwu Designated Cities (JOI19_designated_cities) C++14
16 / 100
 355 ms 79176 KB 
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

template<class X, class Y>
    bool minz(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        } return false;
    }
template<class X, class Y>
    bool maxz(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        } return false;
    }

const int N = 2e5 + 5;
const ll oo = (ll) 1e16;
const ll mod = 1e9 + 7; // 998244353;

ll lz[N << 2], n, lmao[N], par[N], uwu[N], up[N], dw[N], f[N], g[N], tmp[4], dp[N][3],
 fo[N], leafs, tin[N], tout[N], cnt, vis[N], u, v, w, z, q, ans[N], rf[N];
pll tree[N << 2], ed[N], owo[N];
vector <int> a[N];


void down (int i){
    if (!lz[i]) return;
    forr (j, i << 1, i << 1 | 1){
        tree[j].st += lz[i];
        lz[j] += lz[i];
    }
    lz[i] = 0;
}

void add (int i, int l, int r, int u, int v, ll w, ll z){
    if (l > v || r < u) return;
    if (l >= u && r <= v){
        tree[i].st += w;
        tree[i].nd += z;
        lz[i] += w;
        return;
    }
    down(i);
    int mid = l + r >> 1;
    add(i << 1, l, mid, u, v, w, z);
    add(i << 1 | 1, mid + 1, r, u, v, w, z);
    tree[i] = max(tree[i << 1], tree[i << 1 | 1]);    
}

void dfs (int u, int p){
    uwu[u] = u;
    owo[u] = {u, u};

    for (int i : a[u]){
        int v = u ^ ed[i].st ^ ed[i].nd;
        ll w = up[i], z = dw[i];
        if (u == ed[i].st) swap(w, z);

        if (v == p) continue;

        dfs(v, u);
        rf[u] += rf[v] + z;
        f[u] += f[v] + w;
        
        forr (j, 0, 2){
            tmp[j] = dp[u][j] + dp[v][0] + w;
        }
        
        if (maxz(tmp[2], dp[u][0] + dp[v][2] + z)){
            owo[u] = owo[v];        
        }

        if (maxz(tmp[2], dp[u][1] + dp[v][1] + w + z)){
            owo[u] = {uwu[u], uwu[v]};
        }

        if (maxz(tmp[1], dp[u][0] + dp[v][1] + w + z)){
            uwu[u] = uwu[v];
        }

        forr (i, 0, 2){
            dp[u][i] = tmp[i];
        }
    } 
}

void dfs2 (int u, int p){
   // cout << u << " " << f[u] << " " << fo[u] << " " << rf[u] << endl;
    for (int i : a[u]){
        int v = u ^ ed[i].st ^ ed[i].nd;
        ll w = up[i], z = dw[i];
        if (u == ed[i].st) swap(w, z);
        if (v == p) continue; 

        fo[v] = fo[u] + f[u] - f[v] - w + z;

        dfs2(v, u);
    }
}

void dfs3 (int u, int p){
    tin[u] = ++cnt;
    
    if (a[u].size() == 1 && u != p){
        leafs++;
        add(1, 1, n, tin[u], tin[u], g[u], u);
    }

    for (int i : a[u]){
        int v = u ^ ed[i].st ^ ed[i].nd;
        ll w = up[i], z = dw[i];
        if (u == ed[i].st) swap(w, z);
        if (v == p) continue;

        g[v] = g[u] + z;
        par[v] = u;
        lmao[v] = z;

        dfs3(v, u);
    }

    tout[u] = cnt;
}

void bem (int u, ll w = 0){
    add(1, 1, n, tin[u], tout[u], w, 0);
    if (!vis[u]){
        vis[u] = 1;
        bem(par[u], lmao[u]);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef kaguya
        freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    #endif

    cin >> n;

    ll sum = 0;

    forf (i, 1, n){
        cin >> u >> v >> w >> z;
        ed[i] = {u, v};
        up[i] = w;
        dw[i] = z;
        a[u].pb(i);
        a[v].pb(i);
        sum += w + z;
    }

    dfs(1, 1);
    dfs2(1, 1);

    dfs3(owo[1].st, owo[1].st);
    vis[owo[1].st] = 1;
    leafs++;
  //  cout << owo[1].st << " " << f[owo[1].st] + fo[owo[1].st] << endl;

    forr (i, 2, leafs){
        ans[i] = ans[i - 1] + tree[1].st;

        if (i == 2){
            ans[i] += f[owo[1].st] + fo[owo[1].st];
        }
        bem(tree[1].nd);
    }

    
    forr (i, 1, n){
        maxz(ans[1], f[i] + fo[i]);
    }

    cin >> q;

    while (q--){
        cin >> u;
        cout << sum - ans[min(u, leafs)] << "\n";
    }

    return 0;
}
/*  



*/

Compilation message

designated_cities.cpp: In function 'void add(int, int, int, int, int, ll, ll)':
designated_cities.cpp:66:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14928 KB Output is correct
2 Incorrect 4 ms 16976 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 3 ms 19024 KB Output is correct
2 Correct 282 ms 53056 KB Output is correct
3 Correct 320 ms 71360 KB Output is correct
4 Correct 248 ms 55308 KB Output is correct
5 Correct 242 ms 56184 KB Output is correct
6 Correct 274 ms 57164 KB Output is correct
7 Correct 231 ms 54208 KB Output is correct
8 Correct 355 ms 70472 KB Output is correct
9 Correct 201 ms 48828 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21388 KB Output is correct
2 Correct 272 ms 60936 KB Output is correct
3 Correct 345 ms 79176 KB Output is correct
4 Correct 248 ms 59208 KB Output is correct
5 Correct 250 ms 60944 KB Output is correct
6 Correct 284 ms 63816 KB Output is correct
7 Correct 190 ms 60428 KB Output is correct
8 Correct 331 ms 70988 KB Output is correct
9 Correct 180 ms 56508 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14928 KB Output is correct
2 Incorrect 4 ms 16976 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19024 KB Output is correct
2 Correct 282 ms 53056 KB Output is correct
3 Correct 320 ms 71360 KB Output is correct
4 Correct 248 ms 55308 KB Output is correct
5 Correct 242 ms 56184 KB Output is correct
6 Correct 274 ms 57164 KB Output is correct
7 Correct 231 ms 54208 KB Output is correct
8 Correct 355 ms 70472 KB Output is correct
9 Correct 201 ms 48828 KB Output is correct
10 Correct 3 ms 21388 KB Output is correct
11 Correct 272 ms 60936 KB Output is correct
12 Correct 345 ms 79176 KB Output is correct
13 Correct 248 ms 59208 KB Output is correct
14 Correct 250 ms 60944 KB Output is correct
15 Correct 284 ms 63816 KB Output is correct
16 Correct 190 ms 60428 KB Output is correct
17 Correct 331 ms 70988 KB Output is correct
18 Correct 180 ms 56508 KB Output is correct
19 Correct 5 ms 25168 KB Output is correct
20 Incorrect 281 ms 62536 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14928 KB Output is correct
2 Incorrect 4 ms 16976 KB Output isn't correct
3 Halted 0 ms 0 KB -