oj.uz

Submission #128162

# Submission time Handle Problem Language Result Execution time Memory
128162 2019-07-10T13:26:13 Z mirbek01 Election Campaign (JOI15_election_campaign) C++11
0 / 100
 1000 ms 20668 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], ans;
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);
      }
      int mx = 0;
      for(int i = 0; i < qe[v].size(); i ++){
            int id = qe[v][i];
            int ret = c[id];
            for(int j = tin[v] + 1; j <= tout[v]; j ++)
                  ret += dp[ ver[j] ];
            int vr = a[id];
            while(vr != v){
                  ret -= dp[vr];
                  vr = up[0][vr];
            }
            vr = b[id];
            while(vr != v){
                  ret -= dp[vr];
                  vr = up[0][vr];
            }
            if(mx < ret){
                  mx = ret;
                  dp[v] = c[id];
                  ans = max(ans, mx);
            }
      }
}

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 << ans << endl;
}

Compilation message

election_campaign.cpp: In function 'void calc(int, int)':
election_campaign.cpp:48: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:72:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &n);
       ~~~~~^~~~~~~~~~
election_campaign.cpp:76: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:83:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &m);
       ~~~~~^~~~~~~~~~
election_campaign.cpp:86: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 7 ms 5212 KB Output is correct
2 Correct 8 ms 5112 KB Output is correct
3 Incorrect 7 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 5156 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 5156 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 Execution timed out 1055 ms 20668 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5212 KB Output is correct
2 Correct 8 ms 5112 KB Output is correct
3 Incorrect 7 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 7 ms 5212 KB Output is correct
2 Correct 8 ms 5112 KB Output is correct
3 Incorrect 7 ms 5112 KB Output isn't correct
4 Halted 0 ms 0 KB -