oj.uz

Submission #112743

# Submission time Handle Problem Language Result Execution time Memory
112743 2019-05-21T17:20:52 Z klungs Election Campaign (JOI15_election_campaign) C++14
20 / 100
 1000 ms 60640 KB 
#include<bits/stdc++.h>
 
 
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pf push_front
#define pb2 pop_back
#define pf2 pop_front
#define line printf("\n")
#define pq priority_queue
#define rep(k,i,j) for(int k = (int)i;k<(int)j;k++)
#define repd(k,i,j) for(int k = (int)i;k>=(int)j;k--)
#define ll long long
#define ALL(a) a.begin(),a.end()
#define vi vector<int>
 
using namespace std;
 
int INF = 1e9+7;
 
#define vvi vector<vi>
 
int N, M;
vi A, B, C;
vvi adj;
 
void read(int _N, int _M, vi U, vi V, vi _A, vi _B, vi _C) {
  tie(N, M, A, B, C) = {_N, _M, _A, _B, _C};
  adj.resize(N);
  rep(k, 0, N - 1) {
    U[k]--; V[k]--;
    adj[U[k]].pb(V[k]);
    adj[V[k]].pb(U[k]);
  }
  rep(k, 0, M) {
    A[k]--; B[k]--;
  }
}
 
void bfs(int u, int v, vi &path) {
  vi par(N, -1);
  queue<int> q;
  q.push(u); par[u] = u;
  while (q.size()) {
    int a = q.front(); q.pop();
    for (int b : adj[a]) if (par[b] == -1) {
      q.push(b);
      par[b] = a;
    }
  }
  
  for (int b = v, a = par[v]; b != u; b = par[b], a = par[a]) {
    path.pb(b);    
  }
  path.pb(u);
}
 
vi par, hi;
void dfs(int a, int p) {
  par[a] = p; hi[a] = hi[p] + 1;
  for (int b : adj[a]) if (b != p) {
    dfs(b, a);
  }
}
void make_rooted_tree() { // root at 0
  par = hi = vi(N);
  dfs(0, 0);
}
 
vector<vvi> path;
vvi cost;
 
vi DP, SUM_CH;
int dp(int); int sum_ch(int);
 
int dp(int a) {
  int &ret = DP[a];
  if (ret != -1) return ret;
  
  int sum = sum_ch(a);
  ret = sum;
  rep(k, 0, path[a].size()) {
    int sum_ch_path = 0, c = cost[a][k];
    for (int ch : path[a][k]) {
      sum_ch_path += sum_ch(ch) - dp(ch);
    }
    int cur = sum + sum_ch_path + c;
    ret = max(ret, cur);
  }
  return ret;
}
 
int sum_ch(int a) {
  int &ret = SUM_CH[a];
  if (ret != -1) return ret;
  ret = 0;
  for (auto b : adj[a]) ret += dp(b);
  return ret;
}
 
int getMaximumVotes(int _N, int _M, vi _U, vi _V, vi _A, vi _B, vi _C) {
  read(_N, _M, _U, _V, _A, _B, _C);
  
  make_rooted_tree();
  
  // puts("rooted tree");
  path = vector<vvi>(N); 
  cost = vvi(N);
  rep(k, 0, M) { // prepare
    vi nodes; bfs(A[k], B[k], nodes);
    int uv = A[k];
    for (int a : nodes) // get lca
      if (hi[uv] > hi[a]) 
        uv = a;
    
    vi nodes_wo_lca;
    for (int a : nodes) if(a != uv)
      nodes_wo_lca.pb(a);
      
    path[uv].pb(nodes_wo_lca);
    cost[uv].pb(C[k]);
  }
  
  adj = vvi(N);
  rep(k, 1, N) adj[par[k]].pb(k);
  // puts("prepare");
  
  DP = SUM_CH = vi(N, -1);
  return dp(0);
}
 
// grader.cpp
#include <stdio.h>
#include <vector>
 
int main() {
  int N, M;
  std::vector<int> U, V;
  std::vector<int> A, B, C;
 
  scanf("%d", &N);
  U.resize(N-1); V.resize(N-1);
 
  for (int i = 0 ; i < N-1 ; i++) {
    scanf("%d %d", &U[i], &V[i]);
  }
  scanf("%d", &M);
  A.resize(M); B.resize(M); C.resize(M);
  for (int i = 0 ; i < M ; i++) {
    scanf("%d %d %d", &A[i], &B[i], &C[i]);
  }
 
  int ans = getMaximumVotes(N, M, U, V, A, B, C);
  printf("%d\n", ans);
  
  return 0;
}

Compilation message

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:145:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
   ~~~~~^~~~~~~~~~
election_campaign.cpp:149:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &U[i], &V[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:151:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &M);
   ~~~~~^~~~~~~~~~
election_campaign.cpp:154:10: 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 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 157 ms 16944 KB Output is correct
6 Correct 74 ms 27840 KB Output is correct
7 Correct 156 ms 23432 KB Output is correct
8 Correct 84 ms 17384 KB Output is correct
9 Correct 235 ms 22312 KB Output is correct
10 Correct 93 ms 17512 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 7 ms 724 KB Output is correct
4 Execution timed out 1066 ms 60640 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 7 ms 724 KB Output is correct
4 Execution timed out 1066 ms 60640 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 18268 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 157 ms 16944 KB Output is correct
6 Correct 74 ms 27840 KB Output is correct
7 Correct 156 ms 23432 KB Output is correct
8 Correct 84 ms 17384 KB Output is correct
9 Correct 235 ms 22312 KB Output is correct
10 Correct 93 ms 17512 KB Output is correct
11 Correct 26 ms 640 KB Output is correct
12 Correct 20 ms 2048 KB Output is correct
13 Correct 19 ms 896 KB Output is correct
14 Correct 12 ms 640 KB Output is correct
15 Correct 27 ms 632 KB Output is correct
16 Correct 20 ms 980 KB Output is correct
17 Correct 13 ms 640 KB Output is correct
18 Correct 24 ms 1516 KB Output is correct
19 Correct 12 ms 640 KB Output is correct
20 Correct 19 ms 2048 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 157 ms 16944 KB Output is correct
6 Correct 74 ms 27840 KB Output is correct
7 Correct 156 ms 23432 KB Output is correct
8 Correct 84 ms 17384 KB Output is correct
9 Correct 235 ms 22312 KB Output is correct
10 Correct 93 ms 17512 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 7 ms 724 KB Output is correct
14 Execution timed out 1066 ms 60640 KB Time limit exceeded
15 Halted 0 ms 0 KB -