oj.uz

Submission #486769

# Submission time Handle Problem Language Result Execution time Memory
486769 2021-11-12T18:16:33 Z Nimbostratus Sjekira (COCI20_sjekira) C++17
110 / 110
 185 ms 25156 KB 
#include "bits/stdc++.h"
#define endl '\n'
#define int long long
constexpr int maxn = 1e5+5;
constexpr int mod = 1e9+7;
using namespace std;
using lint = long long;
constexpr lint maxk = 1e9;
constexpr lint inf = 1e18;
using pll = pair<lint, lint>;
 
int n;
lint val[maxn];
vector<int> adj[maxn];
int m, h;
int tin[maxn], tout[maxn], b[2 * maxn], p[maxn];
pll t[4 * maxn];
int lz[2 * maxn];
bool vis[maxn];
lint ans;
     
void dfs(int u) {
    b[m] = u;
    tin[u] = m;
    m++;
    for(int v : adj[u])
        if(v != p[u]) {
            p[v] = u;
            dfs(v);
        }
    b[m] = u;
    tout[u] = m;
    m++;
}

void build() {
    h = 8 * sizeof(int) - __builtin_clz(m);
    for(int i = 0; i < m; i++) {
    	t[m + i].first = val[b[i]];
    	t[m + i].second = b[i];
    }
    for(int i = m - 1; i >= 1; i--) {
        t[i] = max(t[i << 1], t[i << 1 | 1]);
        lz[i] = 1;
    }
}
 
void apply(int u, lint val) {
    t[u].first *= val;
    if(u < m)
        lz[u] *= val;
}
     
void fixup(int u) {
    for(u >>= 1; u; u >>= 1) {
        t[u] = max(t[u << 1], t[u << 1 | 1]);
        t[u].first *= lz[u];
    }
}
     
void push(int u) {
    for(int k = h; k > 0; k--) {
        int s = u >> k;
        if(!s)
            continue;        
        apply(s << 1, lz[s]);
        apply(s << 1 | 1, lz[s]);
        lz[s] = 1;
    }
}
     
void update(int l, int r, lint k) {
    l += m;
    r += m;
    int l0 = l, r0 = r;
    for(; l <= r; l >>= 1, r >>= 1) {
        if(l & 1)
            apply(l++, k);
        if(r + 1 & 1)
            apply(r--, k);
    }
    fixup(l0);
    fixup(r0);
}
     
pll query(int l, int r) {
    pll ret = {-inf, 0};
    if(l > r)
    	return ret;
    l += m;
    r += m;
    push(l);
    push(r);
    for(; l <= r; l >>= 1, r >>= 1) {
        if(l & 1)
            ret = max(ret, t[l++]);
        if(r + 1 & 1)
            ret = max(ret, t[r--]);
    }
    return ret;
}
     
     
void solve(int u) {
    vis[u] = true;
    if(adj[u].size() <= 1) {
    	update(tin[u], tout[u], 0);
        return;
    }
    while(true) {
    	lint x, mx;
        tie(x, mx) = query(tin[u], tout[u]);
        if(u == mx) {
            for(int v : adj[u]) {
                if(vis[v] || p[u] == v)
                    continue;
                ans += x + query(tin[v], tout[v]).first;
                solve(v);
                update(tin[v], tout[v], 0);
            }
            update(tin[u], tout[u], 0);
            return;
        }
        else {
        	lint q1 = query(tin[u], tin[mx] - 1).first;
        	lint q2 = query(tout[mx] + 1, tout[u]).first;
            lint comp2 = max(q1, q2);
            ans += comp2 + x;
            solve(mx);
            update(tin[mx], tout[mx], 0);
        }
    }
    
}
     
     
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> val[i];
    if(n == 1) {
    	cout << 0 << endl;
    	return 0;
    }
    if(n == 2) {
    	cout << val[1] + val[2] << endl;
    	return 0;
    }
    for(int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int root = -1;
    for(int i = 1; i <= n; i++)
        if(adj[i].size() > 1) {
            root = i;
            break;
        }
    dfs(root);
    build();
    solve(root);
    cout << ans << endl;
}

Compilation message

sjekira.cpp: In function 'void update(long long int, long long int, lint)':
sjekira.cpp:79:14: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   79 |         if(r + 1 & 1)
      |            ~~^~~
sjekira.cpp: In function 'pll query(long long int, long long int)':
sjekira.cpp:97:14: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   97 |         if(r + 1 & 1)
      |            ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2680 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 20748 KB Output is correct
2 Correct 93 ms 16732 KB Output is correct
3 Correct 89 ms 16244 KB Output is correct
4 Correct 107 ms 17680 KB Output is correct
5 Correct 156 ms 25116 KB Output is correct
6 Correct 185 ms 25148 KB Output is correct
7 Correct 164 ms 22152 KB Output is correct
8 Correct 145 ms 20384 KB Output is correct
9 Correct 95 ms 14276 KB Output is correct
10 Correct 184 ms 25156 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2680 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2892 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 2 ms 2892 KB Output is correct
10 Correct 3 ms 2816 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2680 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 128 ms 20748 KB Output is correct
7 Correct 93 ms 16732 KB Output is correct
8 Correct 89 ms 16244 KB Output is correct
9 Correct 107 ms 17680 KB Output is correct
10 Correct 156 ms 25116 KB Output is correct
11 Correct 185 ms 25148 KB Output is correct
12 Correct 164 ms 22152 KB Output is correct
13 Correct 145 ms 20384 KB Output is correct
14 Correct 95 ms 14276 KB Output is correct
15 Correct 184 ms 25156 KB Output is correct
16 Correct 2 ms 2892 KB Output is correct
17 Correct 3 ms 2816 KB Output is correct
18 Correct 2 ms 2764 KB Output is correct
19 Correct 2 ms 2892 KB Output is correct
20 Correct 3 ms 2816 KB Output is correct
21 Correct 34 ms 7000 KB Output is correct
22 Correct 35 ms 6220 KB Output is correct
23 Correct 167 ms 20228 KB Output is correct
24 Correct 114 ms 15196 KB Output is correct
25 Correct 109 ms 15076 KB Output is correct
26 Correct 67 ms 10940 KB Output is correct
27 Correct 84 ms 12440 KB Output is correct
28 Correct 137 ms 15680 KB Output is correct
29 Correct 86 ms 11540 KB Output is correct
30 Correct 168 ms 21104 KB Output is correct