oj.uz

Submission #1051310

# Submission time Handle Problem Language Result Execution time Memory
1051310 2024-08-10T04:17:54 Z phong Election Campaign (JOI15_election_campaign) C++17
60 / 100
 257 ms 51416 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

#define ll long long
#define int long long
const int nmax = 1e5 + 5, N = 1e6;
const ll oo = 1e9 + 5, base = 311;
const int lg = 17, tx = 26;
const ll mod = 998244353;
#define pii pair<ll, ll>
#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;
vector<int> adj[nmax];
struct node{
    ll x, y, c;
};
vector<node>Q[nmax];
node a[nmax];
int h[nmax], up[nmax][lg + 1], sz[nmax];
void dfs(int u, int p){
    sz[u] = 1;
    for(auto v : adj[u]){
        if(v == p) continue;
        h[v] = h[u] + 1;
        up[v][0] = u;
        for(int j = 1; j <= lg; ++j)up[v][j] = up[up[v][j - 1]][j - 1];
        dfs(v, u);
        sz[u] += sz[v];
    }
}

int lca(int u, int v){
    if(h[u] != h[v]){
        if(h[u] < h[v]) swap(u, v);
        int k = h[u] - h[v];
        for(int j = 0; j <= lg; ++j){
            if(k >> j & 1){
                u = up[u][j];
            }
        }
    }
    if(u == v) return u;
    for(int j = lg; j >= 0; --j){
        if(up[u][j] != up[v][j]){
            u = up[u][j];
            v = up[v][j];
        }
    }
    return up[u][0];
}

int nchain = 1, m = 0, pos[nmax], ind[nmax], head[nmax];
int fly(int u, int a){
    int k = h[u] - h[a] - 1;
    if(k < 0) return -1;
    for(int j = 0; j <= lg; ++j){
        if(k >> j & 1) u = up[u][j];
    }
    return u;
}
void dfs_2(int u, int p){
    if(!head[nchain]) head[nchain] = u;
    pos[u]= ++m;
    ind[u] = nchain;
    int idx = -1;
    for(auto v : adj[u]){
        if(v == p) continue;
        if(idx == -1 || sz[v]> sz[idx]){
            idx = v;
        }
    }
    if(idx != -1) dfs_2(idx, u);
    for(auto v: adj[u]){
        if(v == p || v == idx) continue;
        ++nchain;
        dfs_2(v, u);
    }
}
struct hld1{
    ll tree[nmax << 2];
    void update(int id, int l, int r, int u, ll val){
        if(l > u || r < u) return;
        if(l == r){
            tree[id] = val;
            return;
        }
        int mid = r + l >> 1;
        update(id << 1, l, mid, u, val);
        update(id << 1 | 1, mid + 1, r, u, val);
        tree[id] = tree[id << 1] + tree[id << 1 | 1];
    }
    ll get(int id, int l, int r, int u, int v){
        if(l >= u && r <= v) return tree[id];
        int mid = r + l >> 1;
        if(mid < u) return get(id << 1 | 1, mid + 1, r, u, v);
        if(mid + 1 > v) return get(id << 1, l, mid, u, v);
        return get(id << 1, l, mid, u, v) + get(id << 1| 1, mid + 1, r, u, v);
    }
    ll get(int u, int a){
        int uchain = ind[u], achain = ind[a];
        ll res = 0;
        while(1){
            if(achain == uchain){
                res += get(1, 1, n, pos[a], pos[u]);
                return res;
            }
            res += get(1, 1, n, pos[head[uchain]], pos[u]);
            u = up[u][0];
            uchain = ind[u];
        }
    }
    void update(int u, ll  val){
        update(1, 1, n, pos[u], val);
    }
}A[2];
ll f[nmax][2];
void dfs_3(int u, int p){
    ll sum = 0;
    for(auto v : adj[u]){
        if(v == p) continue;
        dfs_3(v, u);
        sum += max(f[v][0], f[v][1]);
    }
    for(auto [x, y, c] : Q[u]){
        int t1 = fly(x, u);
        int t2 = fly(y, u);
       ll cur = 0;
        if(t1 != -1){
            cur += A[0].get(x, t1);
            cur -= A[1].get(x, t1);
        }
        if(t2 != -1){
            cur += A[0].get(y, t2);
            cur -= A[1].get(y, t2);

        }
//        if(u == 5) cout << c << ' ' << cur <<endl;

        cur += sum;

        f[u][1] = max(f[u][1], cur + c);
    }
    f[u][0] = sum;
    A[0].update(u, sum);

    A[1].update(u, max(f[u][1], f[u][0]));
//    cout << u << ' ' << max(f[u][0], f[u][1]) << ' ' << A[0].get(u, u) << endl;
}
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;
    for(int i = 1; i < n; ++i){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, -1);
    int m;
    cin >>m;
    for(int i = 1; i <= m; ++i){
        cin >> a[i].x >> a[i].y >> a[i].c;
        int lc = lca(a[i].x, a[i].y);
        Q[lc].push_back(a[i]);
    }
    dfs_2(1, -1);
    dfs_3(1, -1);
//    cout << A[0].get(6, 6);
    cout << max(f[1][1], f[1][0]);
}
/*

7
3 4
6 5
2 7
1 5
7 5
4 5
5
4 3 10
5 6 5
2 6 9
7 2 2
1 3 8



*/

Compilation message

election_campaign.cpp: In member function 'void hld1::update(long long int, long long int, long long int, long long int, long long int)':
election_campaign.cpp:94:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |         int mid = r + l >> 1;
      |                   ~~^~~
election_campaign.cpp: In member function 'long long int hld1::get(long long int, long long int, long long int, long long int, long long int)':
election_campaign.cpp:101:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |         int mid = r + l >> 1;
      |                   ~~^~~
election_campaign.cpp: At global scope:
election_campaign.cpp:156:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  156 | main(){
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5460 KB Output is correct
4 Correct 2 ms 5468 KB Output is correct
5 Correct 53 ms 32176 KB Output is correct
6 Correct 44 ms 45240 KB Output is correct
7 Correct 65 ms 40788 KB Output is correct
8 Correct 50 ms 32848 KB Output is correct
9 Correct 61 ms 38096 KB Output is correct
10 Correct 43 ms 32712 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5468 KB Output is correct
4 Correct 107 ms 50940 KB Output is correct
5 Correct 108 ms 51416 KB Output is correct
6 Correct 85 ms 51020 KB Output is correct
7 Correct 104 ms 51280 KB Output is correct
8 Correct 105 ms 51032 KB Output is correct
9 Correct 89 ms 51024 KB Output is correct
10 Correct 118 ms 51028 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5468 KB Output is correct
4 Correct 107 ms 50940 KB Output is correct
5 Correct 108 ms 51416 KB Output is correct
6 Correct 85 ms 51020 KB Output is correct
7 Correct 104 ms 51280 KB Output is correct
8 Correct 105 ms 51032 KB Output is correct
9 Correct 89 ms 51024 KB Output is correct
10 Correct 118 ms 51028 KB Output is correct
11 Correct 11 ms 7000 KB Output is correct
12 Correct 128 ms 51052 KB Output is correct
13 Correct 107 ms 51024 KB Output is correct
14 Correct 88 ms 51024 KB Output is correct
15 Correct 113 ms 51028 KB Output is correct
16 Correct 85 ms 51024 KB Output is correct
17 Correct 105 ms 51080 KB Output is correct
18 Correct 108 ms 51024 KB Output is correct
19 Correct 89 ms 51108 KB Output is correct
20 Correct 113 ms 51024 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 37640 KB Output is correct
2 Correct 84 ms 51044 KB Output is correct
3 Correct 168 ms 46240 KB Output is correct
4 Correct 108 ms 38332 KB Output is correct
5 Correct 126 ms 44940 KB Output is correct
6 Correct 107 ms 38080 KB Output is correct
7 Correct 185 ms 44804 KB Output is correct
8 Correct 144 ms 37572 KB Output is correct
9 Correct 87 ms 50988 KB Output is correct
10 Correct 175 ms 43012 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5460 KB Output is correct
4 Correct 2 ms 5468 KB Output is correct
5 Correct 53 ms 32176 KB Output is correct
6 Correct 44 ms 45240 KB Output is correct
7 Correct 65 ms 40788 KB Output is correct
8 Correct 50 ms 32848 KB Output is correct
9 Correct 61 ms 38096 KB Output is correct
10 Correct 43 ms 32712 KB Output is correct
11 Correct 2 ms 5468 KB Output is correct
12 Correct 4 ms 5468 KB Output is correct
13 Correct 2 ms 5592 KB Output is correct
14 Correct 3 ms 5468 KB Output is correct
15 Correct 2 ms 5468 KB Output is correct
16 Correct 2 ms 5468 KB Output is correct
17 Correct 2 ms 5468 KB Output is correct
18 Correct 3 ms 5468 KB Output is correct
19 Correct 2 ms 5468 KB Output is correct
20 Correct 2 ms 5468 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5460 KB Output is correct
4 Correct 2 ms 5468 KB Output is correct
5 Correct 53 ms 32176 KB Output is correct
6 Correct 44 ms 45240 KB Output is correct
7 Correct 65 ms 40788 KB Output is correct
8 Correct 50 ms 32848 KB Output is correct
9 Correct 61 ms 38096 KB Output is correct
10 Correct 43 ms 32712 KB Output is correct
11 Correct 2 ms 5212 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 2 ms 5468 KB Output is correct
14 Correct 107 ms 50940 KB Output is correct
15 Correct 108 ms 51416 KB Output is correct
16 Correct 85 ms 51020 KB Output is correct
17 Correct 104 ms 51280 KB Output is correct
18 Correct 105 ms 51032 KB Output is correct
19 Correct 89 ms 51024 KB Output is correct
20 Correct 118 ms 51028 KB Output is correct
21 Correct 11 ms 7000 KB Output is correct
22 Correct 128 ms 51052 KB Output is correct
23 Correct 107 ms 51024 KB Output is correct
24 Correct 88 ms 51024 KB Output is correct
25 Correct 113 ms 51028 KB Output is correct
26 Correct 85 ms 51024 KB Output is correct
27 Correct 105 ms 51080 KB Output is correct
28 Correct 108 ms 51024 KB Output is correct
29 Correct 89 ms 51108 KB Output is correct
30 Correct 113 ms 51024 KB Output is correct
31 Correct 257 ms 37640 KB Output is correct
32 Correct 84 ms 51044 KB Output is correct
33 Correct 168 ms 46240 KB Output is correct
34 Correct 108 ms 38332 KB Output is correct
35 Correct 126 ms 44940 KB Output is correct
36 Correct 107 ms 38080 KB Output is correct
37 Correct 185 ms 44804 KB Output is correct
38 Correct 144 ms 37572 KB Output is correct
39 Correct 87 ms 50988 KB Output is correct
40 Correct 175 ms 43012 KB Output is correct
41 Correct 2 ms 5468 KB Output is correct
42 Correct 4 ms 5468 KB Output is correct
43 Correct 2 ms 5592 KB Output is correct
44 Correct 3 ms 5468 KB Output is correct
45 Correct 2 ms 5468 KB Output is correct
46 Correct 2 ms 5468 KB Output is correct
47 Correct 2 ms 5468 KB Output is correct
48 Correct 3 ms 5468 KB Output is correct
49 Correct 2 ms 5468 KB Output is correct
50 Correct 2 ms 5468 KB Output is correct
51 Incorrect 146 ms 37520 KB Output isn't correct
52 Halted 0 ms 0 KB -