Submission #1051319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051319		phong	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	203 ms	53916 KiB

election_campaign

//#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[head[uchain]][0];
            uchain = ind[u];
        }
    }
    void update(int u, ll  val){
        update(1, 1, n, pos[u], val);
    }
}A[2];
ll f[nmax][2];
ll ans = 0;
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);

        }
        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]));
}
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 << max(f[1][0], f[1][1]);
}
/*

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 (stderr)

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:152:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  152 | main(){
      | ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 30 / 30
• Subtask 5: 10 / 10
• Subtask 6: 40 / 40