oj.uz

Submission #128200

# Submission time Handle Problem Language Result Execution time Memory
128200 2019-07-10T14:02:42 Z mirbek01 Election Campaign (JOI15_election_campaign) C++11
20 / 100
 1000 ms 30712 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];
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];
            int vr = a[id];
            while(vr != v){
                  if(up[0][vr] != v){
                        for(int to : g[ up[0][vr] ]){
                              if(to == up[1][vr] || to == vr)
                                    continue;
                              ret += dp[to];
                        }
                  }
                  vr = up[0][vr];
            }
            vr = b[id];
            while(vr != v){
                  if(up[0][vr] != v){
                        for(int to : g[ up[0][vr] ]){
                              if(to == up[1][vr] || to == vr)
                                    continue;
                              ret += dp[to];
                        }
                  }
                  vr = up[0][vr];
            }
            for(int to : g[v]){
                  if(to == pr || upper(to, a[id]) || upper(to, b[id]))
                        continue;
                  ret += dp[to];
            }
            if(v != a[id]){
                  for(int to : g[ a[id] ]){
                        if(to == up[0][ a[id] ])
                              continue;
                        ret += dp[to];
                  }
            }
            if(v != b[id]){
                  for(int to : g[ b[id] ]){
                        if(to == up[0][ b[id] ])
                              continue;
                        ret += dp[to];
                  }
            }
            dp[v] = max(dp[v], ret);
      }
}

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:54: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:103:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &n);
       ~~~~~^~~~~~~~~~
election_campaign.cpp:107: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:114:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &m);
       ~~~~~^~~~~~~~~~
election_campaign.cpp:117: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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5240 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5116 KB Output is correct
4 Correct 9 ms 5368 KB Output is correct
5 Correct 178 ms 17796 KB Output is correct
6 Correct 69 ms 26872 KB Output is correct
7 Correct 139 ms 23616 KB Output is correct
8 Correct 118 ms 18168 KB Output is correct
9 Correct 153 ms 21844 KB Output is correct
10 Correct 116 ms 18040 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 8 ms 5368 KB Output is correct
4 Execution timed out 1061 ms 30612 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 8 ms 5368 KB Output is correct
4 Execution timed out 1061 ms 30612 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 19664 KB Output is correct
2 Execution timed out 1060 ms 30712 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5240 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5116 KB Output is correct
4 Correct 9 ms 5368 KB Output is correct
5 Correct 178 ms 17796 KB Output is correct
6 Correct 69 ms 26872 KB Output is correct
7 Correct 139 ms 23616 KB Output is correct
8 Correct 118 ms 18168 KB Output is correct
9 Correct 153 ms 21844 KB Output is correct
10 Correct 116 ms 18040 KB Output is correct
11 Correct 8 ms 5244 KB Output is correct
12 Correct 9 ms 5368 KB Output is correct
13 Correct 10 ms 5368 KB Output is correct
14 Correct 10 ms 5240 KB Output is correct
15 Correct 9 ms 5240 KB Output is correct
16 Correct 9 ms 5240 KB Output is correct
17 Correct 10 ms 5240 KB Output is correct
18 Correct 10 ms 5368 KB Output is correct
19 Correct 8 ms 5240 KB Output is correct
20 Correct 10 ms 5368 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5240 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 7 ms 5116 KB Output is correct
4 Correct 9 ms 5368 KB Output is correct
5 Correct 178 ms 17796 KB Output is correct
6 Correct 69 ms 26872 KB Output is correct
7 Correct 139 ms 23616 KB Output is correct
8 Correct 118 ms 18168 KB Output is correct
9 Correct 153 ms 21844 KB Output is correct
10 Correct 116 ms 18040 KB Output is correct
11 Correct 7 ms 5112 KB Output is correct
12 Correct 7 ms 5112 KB Output is correct
13 Correct 8 ms 5368 KB Output is correct
14 Execution timed out 1061 ms 30612 KB Time limit exceeded
15 Halted 0 ms 0 KB -