Submission #444199

#	Time	Username	Problem	Language	Result	Execution time	Memory
444199		ivan_tudor	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	171 ms	32472 KiB

election_campaign

#include<bits/stdc++.h>
using namespace std;
struct AIB{
  vector<int> aib;
  AIB(int n): aib(n + 1, 0){}
  void update(int poz, int val){
    for(int i = poz; i < aib.size(); i+= i &(-i))
      aib[i] += val;
  }
  int query(int poz){
    int ans = 0;
    for(int i = poz; i > 0; i-= i&(-i))
      ans += aib[i];
    return ans;
  }
  int getonint(int l, int r){
    if(l > r)
      return 0;
    return query(r) - query(l - 1);
  }
};
struct pathlca{
  int x, y;
  int c;
};
const int N = 100005;
const int LOG_N = 17;
vector<int> gr[N];
vector<pathlca> path[N];
int dp[N];
int dpson[N];
AIB sdp(2*N);
AIB sdpson(2*N);
int first[N], last[N];
int par[LOG_N][N];
int h[N];
void dfs_prec(int nod, int dad, int &cnt){
  h[nod] = h[dad] + 1;
  par[0][nod] = dad;
  first[nod] = ++cnt;
  for(auto x:gr[nod]){
    if(x != dad)
      dfs_prec(x, nod, cnt);
  }
  last[nod] = ++cnt;
}
void prec_lca(int n){
  int aux = 0;
  dfs_prec(1, 0, aux);
  for(int log = 1; log < LOG_N; log++){
    for(int i = 1; i <= n; i++){
      par[log][i] = par[log - 1][par[log - 1][i]];
    }
  }
}
bool is_parent(int x, int y){
  if(first[x] <= first[y] && last[y] <= last[x])
    return true;
  return false;
}
int get_lca(int x, int y){
  if(h[x] > h[y])
    swap(x, y);
  if(is_parent(x, y))
    return x;
  for(int pas = LOG_N - 1; pas >= 0; pas--){
    int old_dad = par[pas][x];
    if(old_dad !=0 && is_parent(old_dad, y) == false)
      x = old_dad;
  }
  return par[0][x];
}
int getsumpath(int x, int y, int p, AIB &sums){
  int sum = sums.getonint(first[p], first[x]) + sums.getonint(first[p] + 1, first[y]);
  return sum;
}
void addtonode(int nod, int val, AIB &sums){
  if(nod == 0)
    return;
  sums.update(first[nod], val);
  sums.update(last[nod], -val);
}
void dfs(int nod, int dad){
  int dpnod = 0;
  for(auto x:gr[nod])
    if(x!=dad){
      dfs(x, nod);
    }
  dpnod = dpson[nod];
  for(auto tri:path[nod]){
    int x = tri.x, y = tri.y, c = tri.c;
    int sum = getsumpath(x, y, nod, sdp);
    int sumson = getsumpath(x, y, nod, sdpson);
    dpnod = max(dpnod, sumson - sum + c);
  }
  dp[nod] = dpnod;
  addtonode(nod, dpnod, sdp);
  dpson[par[0][nod]] += dpnod;
  addtonode(par[0][nod], dpnod, sdpson);
}

int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n;
  cin>>n;
  for(int i = 1; i < n; i++){
    int x, y;
    cin>>x>>y;
    gr[x].push_back(y);
    gr[y].push_back(x);
  }
  int m;
  prec_lca(n);
  cin>>m;
  for(int i = 1; i <=m; i++){
    int x, y, c;
    cin>>x>>y>>c;
    int lca = get_lca(x, y);
    path[lca].push_back({x, y, c});
  }
  dfs(1, 0);
  cout<<dp[1];
  return 0;
}

Compilation message (stderr)

election_campaign.cpp: In member function 'void AIB::update(int, int)':
election_campaign.cpp:7:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 |     for(int i = poz; i < aib.size(); i+= i &(-i))
      |                      ~~^~~~~~~~~~~~

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