Submission #444693

#TimeUsernameProblemLanguageResultExecution timeMemory
444693NintsiChkhaidzeElection Campaign (JOI15_election_campaign)C++14
100 / 100
536 ms48948 KiB
#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define ll long long
#define pii pair<int,int>
#define left (node<<1),l,((l+r)>>1)
#define right ((node<<1)|1),((l+r)>>1) + 1,r
#define int ll
using namespace std;
const int N = 100005;
int cnt,a[N],d[25][N],dep[N],dp[N],in[N],out[N],fen[N];
vector <int> v[N];
set <pii> st;
vector <pair<pii,int> > vec[N];
void dfs(int x,int par){
    dep[x] = dep[par] + 1;
    in[x] = ++cnt;
    d[0][x] = par;
    for (int j = 0; j < v[x].size(); j++){
        int to = v[x][j];
        if (to != par) dfs(to,x);
    }
    out[x] = cnt;
}
void upd(int ind,int val){
    while(ind <= N){
        fen[ind] += val;
        ind += (ind&(-ind));
    }
}
int get(int ind){
    int s=0;
    while(ind){
        s += fen[ind];
        ind -= (ind&(-ind));
    }
    return s;
}
void solve(int x){
    int S = 0;
    for (int j = 0; j < v[x].size(); j++){
        int to = v[x][j];
        if (to == d[0][x]) continue;
        solve(to);
        S += dp[to];
    }
    dp[x] = S;
    upd(in[x], S);
    upd(in[x] + 1,-S);
    
    st.clear(); st.insert({N,0});
    for (int j = 0; j < v[x].size(); j++){
        int to = v[x][j];
        if (to == d[0][x]) continue;
        st.insert({in[to],dp[to]});
    }
    
    for (int j = 0; j < vec[x].size(); j++){
        int l = vec[x][j].f.f,r = vec[x][j].f.s;
        int s = vec[x][j].s + S;
        set <pii> :: iterator it;
        
        if (l != x){
            s += get(in[l]);
            it = st.lower_bound({in[l],1e18});
            it--;
            s -= (it->s);
        } 
        
        if (r != x){
            s += get(in[r]);
            it = st.lower_bound({in[r],1e18});
            it--;
            s -= (it->s);
        } 
    
        dp[x] = max(dp[x],s);
    }
    
    for (int j = 0; j < v[x].size(); j++){
        int to = v[x][j];
        if (to == d[0][x]) continue;
        S -= dp[to];
        upd(in[to], S);
        upd(out[to] + 1,-S);
        S += dp[to];
    }
}
int lca(int x,int y){
    if (dep[x] > dep[y]) swap(x,y);
    
    for (int j = 20; j >= 0; j--)
        if (dep[d[j][y]] >= dep[x]) y = d[j][y];
        
    if (x == y) return x;   
    
    for (int j = 20; j >= 0; j--)
        if (d[j][x] != d[j][y]) x = d[j][x],y = d[j][y];
    
    return d[0][x];
}
main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    int n;
    cin>>n;
    for (int i =1; i <n;i++){
        int a,b;
        cin>>a>>b;
        v[a].pb(b),v[b].pb(a);
    }
    dfs(1,1);
    
    for (int i = 1; i <= 20; i++)
        for (int j = 1; j <= n; j++)
            d[i][j] = d[i - 1][d[i - 1][j]];
    
    int q;
    cin>>q;
    while(q--){
        int x,y,z;
        cin>>x>>y>>z;
        int c = lca(x,y);
        vec[c].pb({{x,y},z});
    }
    
    solve(1);
    cout<<dp[1];
}

Compilation message (stderr)

election_campaign.cpp: In function 'void dfs(long long int, long long int)':
election_campaign.cpp:20:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int j = 0; j < v[x].size(); j++){
      |                     ~~^~~~~~~~~~~~~
election_campaign.cpp: In function 'void solve(long long int)':
election_campaign.cpp:42:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int j = 0; j < v[x].size(); j++){
      |                     ~~^~~~~~~~~~~~~
election_campaign.cpp:53:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for (int j = 0; j < v[x].size(); j++){
      |                     ~~^~~~~~~~~~~~~
election_campaign.cpp:59:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int j = 0; j < vec[x].size(); j++){
      |                     ~~^~~~~~~~~~~~~~~
election_campaign.cpp:81:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int j = 0; j < v[x].size(); j++){
      |                     ~~^~~~~~~~~~~~~
election_campaign.cpp: At global scope:
election_campaign.cpp:103:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  103 | main (){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...