Submission #657828

#	Time	Username	Problem	Language	Result	Execution time	Memory
657828		Do_you_copy	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	472 ms	35248 KiB

election_campaign

/*
    Procrastination is the art of keeping up with yesterday
*/
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
#define int long long
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e5 + 1;
//const int Mod = 1e9 + 7;
//const int inf =
int n, q;

struct TST{
    vector <ll> st;
    void resize(int _n){
        st.resize(_n, 0);
    }
    void update(int id, int i, ll val, int l = 1, int r = n){
        if (l == r){
            st[id] = val;
            return;
        }
        int mid = (l + r) >> 1;
        if (i <= mid) update(id << 1, i, val, l, mid);
        else update(id << 1 | 1, i, val, mid + 1, r);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }
    int get(int id, int i, int j, int l = 1, int r = n){
        if (i > r || l > j) return 0;
        if (i <= l && r <= j) return st[id];
        int mid = (l + r) >> 1;
        return get(id << 1, i, j, l, mid) + get(id << 1 | 1, i, j, mid + 1, r);
    }
};
TST tree[2];

struct TLine{
    int u, v, c;
};

TLine e[maxN];
vector <int> adj[maxN];
vector <int> Q[maxN];
int child[maxN];
int id[maxN], num[maxN], timedfs, nodecnt = 1;
int head[maxN], tail[maxN];
int depth[maxN];
int par[maxN];
ll dp[maxN];

inline int lca(int u, int v){
    while (id[u] != id[v]){
        if (depth[head[id[u]]] < depth[head[id[v]]]) swap(u, v);
        u = par[head[id[u]]];
    }
    if (depth[u] < depth[v]) swap(u, v);
    return v;
}

inline ll Query(int u, int v, int t){
    int res = 0;
    while (id[u] != id[v]){
        if (depth[head[id[u]]] < depth[head[id[v]]]) swap(u, v);
        res += tree[t].get(1, num[head[id[u]]], num[u]);
        u = par[head[id[u]]];
    }
    if (depth[u] < depth[v]) swap(u, v);
    res += tree[t].get(1, num[v], num[u]);
    return res;
}

void pre_dfs(int u, int p){
    depth[u] = depth[p] + 1;
    par[u] = p;
    for (int i: adj[u]){
        if (i == p) continue;
        pre_dfs(i, u);
        child[u] += child[i] + 1;
    }
}

void hld(int u){
    if (!head[nodecnt]) head[nodecnt] = u;
    id[u] = nodecnt;
    num[u] = ++timedfs;
    pii maxx = {-1, -1};
    for (int i: adj[u]){
        if (i == par[u]) continue;
        maxx = max(maxx, {child[i], i});
    }
    if (maxx.se != -1){
        hld(maxx.se);
    }
    else tail[nodecnt] = u;
    for (int i: adj[u]){
        if (i == par[u] || i == maxx.se) continue;
        ++nodecnt;
        hld(i);
    }
}


void dfs(int u){
    ll sum = 0;
    for (int i: adj[u]){
        if (i == par[u]) continue;
        dfs(i);
        sum += dp[i];
    }
    dp[u] = sum;
    tree[0].update(1, num[u], dp[u]);
    for (int i: Q[u]){
        dp[u] = max(dp[u], Query(e[i].u, e[i].v, 0) - Query(e[i].u, e[i].v, 1) + e[i].c);
    }
    tree[1].update(1, num[u], dp[u]);
}

void Init(){
    cin >> n;
    for (int i = 1; i < n; ++i){
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    pre_dfs(1, 0);
    hld(1);
    tree[0].resize(maxN * 4);
    tree[1].resize(maxN * 4);
    cin >> q;
    for (int i = 1; i <= q; ++i){
        cin >> e[i].u >> e[i].v >> e[i].c;
        Q[lca(e[i].u, e[i].v)].pb(i);
    }
    dfs(1);
    cout << dp[1];
}

#define debug
#define taskname "test"
signed main(){
    faster
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    int tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
    if (fopen("timeout.txt", "r")){
        ofstream timeout("timeout.txt");
        timeout << signed(double(clock()) / CLOCKS_PER_SEC * 1000);
        timeout.close();
        #ifndef debug
        cerr << "Time elapsed: " << signed(double(clock()) / CLOCKS_PER_SEC * 1000) << "ms\n";
        #endif // debug
    }
}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:151:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:152:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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