oj.uz

Submission #1115275

# Submission time Handle Problem Language Result Execution time Memory
1115275 2024-11-20T09:44:25 Z hqminhuwu Designated Cities (JOI19_designated_cities) C++14
16 / 100
 350 ms 73032 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 4 ms 23120 KB Output is correct
2 Incorrect 4 ms 21072 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 25168 KB Output is correct
2 Correct 234 ms 54944 KB Output is correct
3 Correct 292 ms 73032 KB Output is correct
4 Correct 234 ms 53832 KB Output is correct
5 Correct 233 ms 54468 KB Output is correct
6 Correct 254 ms 57160 KB Output is correct
7 Correct 230 ms 54208 KB Output is correct
8 Correct 350 ms 70480 KB Output is correct
9 Correct 187 ms 54204 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23120 KB Output is correct
2 Correct 301 ms 60396 KB Output is correct
3 Correct 346 ms 72776 KB Output is correct
4 Correct 242 ms 59108 KB Output is correct
5 Correct 213 ms 55236 KB Output is correct
6 Correct 263 ms 57544 KB Output is correct
7 Correct 166 ms 59324 KB Output is correct
8 Correct 304 ms 64656 KB Output is correct
9 Correct 161 ms 50876 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23120 KB Output is correct
2 Incorrect 4 ms 21072 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 25168 KB Output is correct
2 Correct 234 ms 54944 KB Output is correct
3 Correct 292 ms 73032 KB Output is correct
4 Correct 234 ms 53832 KB Output is correct
5 Correct 233 ms 54468 KB Output is correct
6 Correct 254 ms 57160 KB Output is correct
7 Correct 230 ms 54208 KB Output is correct
8 Correct 350 ms 70480 KB Output is correct
9 Correct 187 ms 54204 KB Output is correct
10 Correct 4 ms 23120 KB Output is correct
11 Correct 301 ms 60396 KB Output is correct
12 Correct 346 ms 72776 KB Output is correct
13 Correct 242 ms 59108 KB Output is correct
14 Correct 213 ms 55236 KB Output is correct
15 Correct 263 ms 57544 KB Output is correct
16 Correct 166 ms 59324 KB Output is correct
17 Correct 304 ms 64656 KB Output is correct
18 Correct 161 ms 50876 KB Output is correct
19 Correct 4 ms 25168 KB Output is correct
20 Incorrect 311 ms 60324 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 23120 KB Output is correct
2 Incorrect 4 ms 21072 KB Output isn't correct
3 Halted 0 ms 0 KB -