Submission #444677

#TimeUsernameProblemLanguageResultExecution timeMemory
444677NintsiChkhaidzeElection Campaign (JOI15_election_campaign)C++14
10 / 100
516 ms46532 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],sum[N],in[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);
    }
}
void solve(int x){
    for (int j = 0; j < v[x].size(); j++){
        int to = v[x][j];
        if (to == d[0][x]) continue;
        solve(to);
        sum[x] += dp[to];
    }
    
    dp[x] = sum[x];
    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 + sum[x];
        set <pii> :: iterator it; 
        if (l != x){
            s += sum[l];
            it = st.lower_bound({in[l],1e18});
            it--;
            s -= (it->s);
        } 
        
        if (r != x){
            s += sum[r];
            it = st.lower_bound({in[r],1e18});
            it--;
            s -= (it->s);
        } 
        dp[x] = max(dp[x],s);
    }
    //cout<<x<<" ans "<<dp[x]<<endl;
}
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:26: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]
   26 |     for (int j = 0; j < v[x].size(); j++){
      |                     ~~^~~~~~~~~~~~~
election_campaign.cpp:35: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]
   35 |     for (int j = 0; j < v[x].size(); j++){
      |                     ~~^~~~~~~~~~~~~
election_campaign.cpp:41: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]
   41 |     for (int j = 0; j < vec[x].size(); j++){
      |                     ~~^~~~~~~~~~~~~~~
election_campaign.cpp: At global scope:
election_campaign.cpp:75:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   75 | 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...