Submission #529241

#	Time	Username	Problem	Language	Result	Execution time	Memory
529241		AdamGS	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	192 ms	25604 KiB

election_campaign

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
vector<int>V[LIM];
vector<pair<pair<int,int>,ll>>P[LIM];
int ojciec[LIM], pierwszy[LIM], odleglosc[LIM], rozmiar[LIM], numer[LIM], akt;
ll tr[4*LIM], dp[LIM], N=1; // w wierzcholku trzymam sum(dp[syn])-dp[x]
void DFS(int x, int o) {
  rozmiar[x]=1;
  ojciec[x]=o;
  for(auto i : V[x]) if(i!=o) {
    odleglosc[i]=odleglosc[x]+1;
    DFS(i, x);
    rozmiar[x]+=rozmiar[i];
  }
  rep(i, V[x].size()) if(V[x][0]==o || rozmiar[V[x][i]]>rozmiar[V[x][0]])
    swap(V[x][0], V[x][i]);
}
void DFS2(int x, int o) {
  numer[x]=akt; ++akt;
  if(V[x][0]!=o) pierwszy[V[x][0]]=pierwszy[x];
  for(auto i : V[x]) if(i!=o) DFS2(i, x);
}
void upd(int v, ll x) {
  v+=N;
  while(v) {
    tr[v]+=x;
    v/=2;
  }
}
ll cnt(int l, int r) {
  l+=N; r+=N;
  ll ans=tr[l];
  if(l!=r) ans+=tr[r];
  while(l/2!=r/2) {
    if(l%2==0) ans+=tr[l+1];
    if(r%2==1) ans+=tr[r-1];
    l/=2; r/=2;
  }
  return ans;
}
int lca(int a, int b) {
  while(pierwszy[a]!=pierwszy[b]) {
    if(odleglosc[pierwszy[a]]<odleglosc[pierwszy[b]]) swap(a, b);
    a=ojciec[pierwszy[a]];
  }
  if(odleglosc[a]>odleglosc[b]) swap(a, b);
  return a;
}
ll sciezka(int a, int b) {
  ll ans=0;
  while(pierwszy[a]!=pierwszy[b]) {
    if(odleglosc[pierwszy[a]]<odleglosc[pierwszy[b]]) swap(a, b);
    ans+=cnt(numer[pierwszy[a]], numer[a]);
    a=ojciec[pierwszy[a]];
  }
  if(odleglosc[a]>odleglosc[b]) swap(a, b);
  ans+=cnt(numer[a], numer[b]);
  return ans;
}
void DFS3(int x, int o) {
  for(auto i : V[x]) if(i!=o) {
    DFS3(i, x);
    dp[x]+=dp[i];
  }
  ll ma=0;
  for(auto i : P[x]) ma=max(ma, sciezka(i.st.st, i.st.nd)+i.nd);
  dp[x]=max(dp[x], ma);
  upd(numer[x], -dp[x]);
  if(x) upd(numer[ojciec[x]], dp[x]);
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n;
  cin >> n;
  while(N<n) N*=2;
  rep(i, n-1) {
    int a, b;
    cin >> a >> b; --a; --b;
    V[a].pb(b);
    V[b].pb(a);
  }
  DFS(0, 0);
  rep(i, n) pierwszy[i]=i;
  DFS2(0, 0);
  int m;
  cin >> m;
  while(m--) {
    int a, b, c;
    cin >> a >> b >> c; --a; --b;
    P[lca(a, b)].pb({{a, b}, c});
  }
  DFS3(0, 0);
  cout << dp[0] << '\n';
}

Compilation message (stderr)

election_campaign.cpp: In function 'void DFS(int, int)':
election_campaign.cpp:4:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
election_campaign.cpp:22:3: note: in expansion of macro 'rep'
   22 |   rep(i, V[x].size()) if(V[x][0]==o || rozmiar[V[x][i]]>rozmiar[V[x][0]])
      |   ^~~

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