oj.uz

Submission #444191

# Submission time Handle Problem Language Result Execution time Memory
444191 2021-07-13T09:53:50 Z ivan_tudor Election Campaign (JOI15_election_campaign) C++14
10 / 100
 161 ms 34088 KB 
#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 = max(dpnod, dp[x]);
    }
  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

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6604 KB Output is correct
2 Correct 4 ms 6604 KB Output is correct
3 Correct 4 ms 6612 KB Output is correct
4 Incorrect 4 ms 6732 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6604 KB Output is correct
2 Correct 4 ms 6604 KB Output is correct
3 Correct 5 ms 6860 KB Output is correct
4 Correct 110 ms 33748 KB Output is correct
5 Correct 121 ms 33768 KB Output is correct
6 Correct 105 ms 33760 KB Output is correct
7 Correct 106 ms 33720 KB Output is correct
8 Correct 128 ms 33732 KB Output is correct
9 Correct 107 ms 33716 KB Output is correct
10 Correct 106 ms 33660 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6604 KB Output is correct
2 Correct 4 ms 6604 KB Output is correct
3 Correct 5 ms 6860 KB Output is correct
4 Correct 110 ms 33748 KB Output is correct
5 Correct 121 ms 33768 KB Output is correct
6 Correct 105 ms 33760 KB Output is correct
7 Correct 106 ms 33720 KB Output is correct
8 Correct 128 ms 33732 KB Output is correct
9 Correct 107 ms 33716 KB Output is correct
10 Correct 106 ms 33660 KB Output is correct
11 Correct 13 ms 7620 KB Output is correct
12 Correct 148 ms 33920 KB Output is correct
13 Correct 141 ms 34088 KB Output is correct
14 Correct 133 ms 34012 KB Output is correct
15 Correct 111 ms 33944 KB Output is correct
16 Correct 108 ms 34012 KB Output is correct
17 Correct 111 ms 33896 KB Output is correct
18 Correct 109 ms 34008 KB Output is correct
19 Correct 110 ms 34020 KB Output is correct
20 Correct 107 ms 33984 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 161 ms 22420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6604 KB Output is correct
2 Correct 4 ms 6604 KB Output is correct
3 Correct 4 ms 6612 KB Output is correct
4 Incorrect 4 ms 6732 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6604 KB Output is correct
2 Correct 4 ms 6604 KB Output is correct
3 Correct 4 ms 6612 KB Output is correct
4 Incorrect 4 ms 6732 KB Output isn't correct
5 Halted 0 ms 0 KB -