Submission #1086530

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1086530	2024-09-11T01:41:12 Z	steveonalex	Election Campaign (JOI15_election_campaign)	C++17	10 / 100	84 ms	31056 KB

election_campaign

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
#define block_of_code if(true)
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(a, b);}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}
 
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
double rngesus_d(double l, double r){
    double cur = rngesus(0, MASK(60) - 1);
    cur /= MASK(60) - 1;
    return l + cur * (r - l);
}
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }
 
template <class T>
    void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }
 
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

const int N = 1e5 + 69, LOG_N = 17;


struct FenwickTree{
    int n;
    vector<ll> a;

    FenwickTree(int _n){
        n = _n;
        a.resize(n+1);
    }

    void update(int i, ll v){
        while(i <= n){
            a[i] += v;
            i += LASTBIT(i);
        }
    }

    void update(int l, int r, ll v){
        update(l, v); update(r + 1, -v);
    }

    ll get(int i){
        ll ans = 0;
        while(i > 0){
            ans += a[i];
            i -= LASTBIT(i);
        }
        return ans;
    }
};

int n, q; 
vector<int> graph[N];
int parent[N][LOG_N], h[N];
int in[N], out[N], dfs_cnt = 0;

void dfs(int u, int p){
    in[u] = ++dfs_cnt;
    h[u] = h[p] + 1;
    for(int j = 1; MASK(j) < h[u]; ++j)
        parent[u][j] = parent[parent[u][j-1]][j-1];
    for(int v: graph[u]) if (v != p){
        parent[v][0] = u;
        dfs(v, u);
        out[u] = out[v];
    }
}

int jump(int u, int d){
    for(int j = 0; j < LOG_N; ++j) if (GETBIT(d, j)) u = parent[u][j];
    return u;
}

int LCA(int u, int v){
    if (h[u] < h[v]) swap(u, v);
    u = jump(u, h[u] - h[v]);
    if (u == v) return u;
    for(int j = LOG_N - 1; j>=0; --j) if (parent[u][j] != parent[v][j]){
        u = parent[u][j];
        v = parent[v][j];
    }
    return parent[u][0];
}

vector<array<int, 3>> queries[N];
ll dp[N], sum[N];
FenwickTree bit(N);


void go(int u, int p){
    for(int v: graph[u]) if (v != p){
        go(v, u);
        sum[u] += dp[v];
        dp[u] += dp[v];
    }

    for(array<int, 3> i: queries[u]){
        int x = i[0], y = i[1], w = i[2];
        ll ans = sum[u] + w;
        ans += bit.get(in[x]) + bit.get(in[y]) - 2 * bit.get(in[u]);
        maximize(dp[u], ans);
    }

    bit.update(in[u], out[u], sum[u] - dp[u]);
}
 
int main(void){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    clock_t start = clock();
 
    cin >> n;
    for(int i = 1; i<n; ++i){
        int u,v; cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    dfs(1, 0);

    cin >> q;
    while(q--){
        int u, v, w; cin >> u >> v >> w;
        queries[LCA(u, v)].push_back({{u, v, w}});
    }

    go(1, 0);

    cout << dp[1] << "\n";
 
    cerr << "Time elapsed: " << clock() - start << " ms\n";
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5980 KB	Output is correct
2	Correct	3 ms	5980 KB	Output is correct
3	Correct	2 ms	5980 KB	Output is correct
4	Correct	76 ms	30548 KB	Output is correct
5	Correct	76 ms	30560 KB	Output is correct
6	Correct	74 ms	30716 KB	Output is correct
7	Correct	79 ms	30548 KB	Output is correct
8	Correct	75 ms	30544 KB	Output is correct
9	Correct	65 ms	30620 KB	Output is correct
10	Correct	81 ms	30708 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5980 KB	Output is correct
2	Correct	3 ms	5980 KB	Output is correct
3	Correct	2 ms	5980 KB	Output is correct
4	Correct	76 ms	30548 KB	Output is correct
5	Correct	76 ms	30560 KB	Output is correct
6	Correct	74 ms	30716 KB	Output is correct
7	Correct	79 ms	30548 KB	Output is correct
8	Correct	75 ms	30544 KB	Output is correct
9	Correct	65 ms	30620 KB	Output is correct
10	Correct	81 ms	30708 KB	Output is correct
11	Correct	9 ms	6748 KB	Output is correct
12	Correct	84 ms	30868 KB	Output is correct
13	Correct	82 ms	30956 KB	Output is correct
14	Correct	77 ms	30920 KB	Output is correct
15	Correct	77 ms	31056 KB	Output is correct
16	Correct	70 ms	31024 KB	Output is correct
17	Correct	79 ms	30800 KB	Output is correct
18	Correct	78 ms	30800 KB	Output is correct
19	Correct	75 ms	30804 KB	Output is correct
20	Correct	79 ms	30800 KB	Output is correct