oj.uz

Submission #1115277

# Submission time Handle Problem Language Result Execution time Memory
1115277 2024-11-20T09:45:41 Z hqminhuwu Designated Cities (JOI19_designated_cities) C++14
16 / 100
 400 ms 75600 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){
    add(1, 1, n, tin[u], tout[u], -lmao[u], 0);
    if (!vis[u]){
        vis[u] = 1;
        bem(par[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 4 ms 5200 KB Output is correct
2 Incorrect 7 ms 5200 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 4 ms 5200 KB Output is correct
2 Correct 307 ms 56648 KB Output is correct
3 Correct 400 ms 75600 KB Output is correct
4 Correct 226 ms 55904 KB Output is correct
5 Correct 244 ms 58076 KB Output is correct
6 Correct 241 ms 57032 KB Output is correct
7 Correct 194 ms 54092 KB Output is correct
8 Correct 340 ms 70604 KB Output is correct
9 Correct 161 ms 51464 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25168 KB Output is correct
2 Correct 208 ms 57928 KB Output is correct
3 Correct 286 ms 72776 KB Output is correct
4 Correct 280 ms 55112 KB Output is correct
5 Correct 259 ms 58416 KB Output is correct
6 Correct 216 ms 57416 KB Output is correct
7 Correct 170 ms 57020 KB Output is correct
8 Correct 333 ms 64628 KB Output is correct
9 Correct 161 ms 51560 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5200 KB Output is correct
2 Correct 307 ms 56648 KB Output is correct
3 Correct 400 ms 75600 KB Output is correct
4 Correct 226 ms 55904 KB Output is correct
5 Correct 244 ms 58076 KB Output is correct
6 Correct 241 ms 57032 KB Output is correct
7 Correct 194 ms 54092 KB Output is correct
8 Correct 340 ms 70604 KB Output is correct
9 Correct 161 ms 51464 KB Output is correct
10 Correct 3 ms 25168 KB Output is correct
11 Correct 208 ms 57928 KB Output is correct
12 Correct 286 ms 72776 KB Output is correct
13 Correct 280 ms 55112 KB Output is correct
14 Correct 259 ms 58416 KB Output is correct
15 Correct 216 ms 57416 KB Output is correct
16 Correct 170 ms 57020 KB Output is correct
17 Correct 333 ms 64628 KB Output is correct
18 Correct 161 ms 51560 KB Output is correct
19 Correct 3 ms 19024 KB Output is correct
20 Incorrect 259 ms 55036 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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