oj.uz

Submission #128489

# Submission time Handle Problem Language Result Execution time Memory
128489 2019-07-11T03:39:02 Z mirbek01 Election Campaign (JOI15_election_campaign) C++11
0 / 100
 256 ms 21556 KB 
# include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

int n, m, a[N], b[N], c[N], dp[N];
int up[17][N], tin[N], tout[N], timer, ver[N];
long long sv[N];
vector <int> g[N], qe[N];

void dfs(int v, int pr){
      tin[v] = ++ timer;
      ver[timer] = v;
      up[0][v] = pr;
      for(int i = 1; i <= 16; i ++)
            up[i][v] = up[i - 1][up[i - 1][v]];
      for(int to : g[v]){
            if(to == pr)
                  continue;
            dfs(to, v);
      }
      tout[v] = timer;
}

bool upper(int a, int b){
      return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b){
      if(upper(a, b))
            return a;
      if(upper(b, a))
            return b;
      for(int i = 16; i >= 0; i --){
            if(!upper(up[i][a], b))
                  a = up[i][a];
      }
      return up[0][a];
}

void calc(int v, int pr){
      for(int to : g[v]){
            if(to == pr)
                  continue;
            calc(to, v);
      }
      long long sum = 0;
      for(int to : g[v]){
            if(to == pr)
                  continue;
            sum += dp[to];
      }
      dp[v] = sum;
      for(int i = 0; i < qe[v].size(); i ++){
            int id = qe[v][i];
            int ret = c[id] + sum;
            int vr = a[id];
            while(vr != v){
                  ret += sv[v];
                  if(a[id] != vr){
                        ret -= dp[vr];
                  }
                  vr = up[0][vr];
            }
            vr = b[id];
            while(vr != v){
                  ret += sv[v];
                  if(b[id] != vr)
                        ret -= dp[vr];
                  vr = up[0][vr];
            }
            dp[v] = max(dp[v], ret);
      }

      for(int to : g[v]){
            if(to == pr)
                  continue;
            sv[v] += dp[to];
      }
}

int main(){
      scanf("%d", &n);

      for(int i = 1; i < n; i ++){
            int u, v;
            scanf("%d %d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
      }

      dfs(1, 1);

      scanf("%d", &m);

      for(int i = 1; i <= m; i ++){
            scanf("%d %d %d", a+i, b+i, c+i);
            qe[ lca(a[i], b[i]) ].push_back(i);
      }

      calc(1, 1);

      cout << dp[1] << endl;
}

Compilation message

election_campaign.cpp: In function 'void calc(int, int)':
election_campaign.cpp:55:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < qe[v].size(); i ++){
                      ~~^~~~~~~~~~~~~~
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:84:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &n);
       ~~~~~^~~~~~~~~~
election_campaign.cpp:88:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &u, &v);
             ~~~~~^~~~~~~~~~~~~~~~~
election_campaign.cpp:95:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &m);
       ~~~~~^~~~~~~~~~
election_campaign.cpp:98:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d %d", a+i, b+i, c+i);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Incorrect 6 ms 5112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Incorrect 6 ms 5112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 40.0

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