Submission #485217

#	Time	Username	Problem	Language	Result	Execution time	Memory
485217		MilosMilutinovic	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	188 ms	35244 KiB

election_campaign

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>


using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


int n,m;

vector<int> graf[100005];

int par[100005][20];
int dep[100005];
int disc[100005];
int out[100005];
int t=1;

void dfs(int u, int p){
    disc[u] = t;
    dep[u] = dep[p] + 1;
    par[u][0] = p;
    ff(i,1,19)par[u][i] = par[par[u][i-1]][i-1];
    for(auto c:graf[u]){
        if(c == p)continue;
        t++;
        dfs(c, u);
    }
    t++;
    out[u] = t;
}

struct sta{
    int a,b,c;
};
vector<sta> st[100005];

ll bit[200005];

void upd(int x, int y){
    while(x < 200005){
        bit[x] += y;
        x += (x&(-x));
    }
}

ll get(int x){
    ll ans = 0;
    while(x > 0){
        ans += bit[x];
        x -= (x&(-x));
    }
    return ans;
}

ll get(int l, int r){
    return get(r) - get(l - 1);
}

bool anc(int u, int v){
    return disc[u] <= disc[v] && out[u] >= out[v];
}

int lca(int u, int v){
    if(anc(u, v))return u;
    if(anc(v, u))return v;
    fb(i,19,0)if(par[u][i] != 0 && !anc(par[u][i], v))u = par[u][i];
    return par[u][0];
}

int dist(int u, int v){
    return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

int lift(int u, int k){
    ff(i,0,19)if(k & (1 << i))u = par[u][i];
    return u;
}

ll dp[100005];

void solve(int u, int p){
    dp[u] = get(disc[u], disc[u]);
    for(auto c:graf[u]){
        if(c == p)continue;
        solve(c, u);
        dp[u] += dp[c];
    }
    for(auto x:st[u]){
        int a = x.a;
        int b = x.b;
        int c = x.c;
        if(anc(b, a))swap(a, b);
        if(a == u){
            dp[u] = max(dp[u], get(disc[u], disc[b]) + c);
        }
        else{
            dp[u] = max(dp[u], get(disc[u], disc[a]) + get(disc[lift(b, dist(b, u) - 1)], disc[b]) + c);
        }
    }
    if(u != 1){
        upd(disc[par[u][0]], dp[u]);
        upd(disc[u], -dp[u]);
        upd(out[u], dp[u]);
        upd(out[par[u][0]], -dp[u]);
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n;
    ff(i,1,n-1){
        int x,y;
        cin >> x >> y;
        graf[x].pb(y);
        graf[y].pb(x);
    }
    dfs(1, 0);
    cin >> m;
    ff(i,1,m){
        int a,b,c;
        cin >> a >> b >> c;
        st[lca(a,b)].pb({a,b,c});
    }
    solve(1, 0);
    cout << dp[1];
    return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'void dfs(int, int)':
election_campaign.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
election_campaign.cpp:37:5: note: in expansion of macro 'ff'
   37 |     ff(i,1,19)par[u][i] = par[par[u][i-1]][i-1];
      |     ^~
election_campaign.cpp: In function 'int lca(int, int)':
election_campaign.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
election_campaign.cpp:81:5: note: in expansion of macro 'fb'
   81 |     fb(i,19,0)if(par[u][i] != 0 && !anc(par[u][i], v))u = par[u][i];
      |     ^~
election_campaign.cpp: In function 'int lift(int, int)':
election_campaign.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
election_campaign.cpp:90:5: note: in expansion of macro 'ff'
   90 |     ff(i,0,19)if(k & (1 << i))u = par[u][i];
      |     ^~
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
election_campaign.cpp:128:5: note: in expansion of macro 'ff'
  128 |     ff(i,1,n-1){
      |     ^~
election_campaign.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
election_campaign.cpp:136:5: note: in expansion of macro 'ff'
  136 |     ff(i,1,m){
      |     ^~

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