Submission #112744

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
112744	2019-05-21T17:23:01 Z	klungs	Election Campaign (JOI15_election_campaign)	C++14	10 / 100	105 ms	24932 KB

election_campaign

#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 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);
}

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]--;
  }
}

vi DP, path, rev;
vvi L, cost;
int dp(int a) {
  if (a < 0) return 0;
  int &ret = DP[a];
  if (ret != -1) return ret;
  
  ret = dp(a - 1);
  rep(k, 0, L[a].size()) {
    int left = L[a][k], val = cost[a][k];
    ret = max(ret, dp(left - 1) + val);
  }
  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);
  
  // check degree
  rep(k, 0, N) if (adj[k].size() > 2) 
    return -1;
  
  vi leaf;
  rep(k, 0, N) if (adj[k].size() == 1)
    leaf.pb(k);
  
  bfs(leaf[0], leaf[1], path);
  rev = vi(N);
  rep(k, 0, N) 
    rev[path[k]] = k;
  
  L = cost = vvi(N);
  rep(k, 0, M) {
    A[k] = rev[A[k]], B[k] = rev[B[k]];
    if (A[k] > B[k]) 
      swap(A[k], B[k]);
      
    L[B[k]].pb(A[k]);
    cost[B[k]].pb(C[k]);
  }
  
  // rep(k, 0, N) printf("%")
  DP = vi(N, -1);
  return dp(N - 1);
}

 
// 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:119:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
   ~~~~~^~~~~~~~~~
election_campaign.cpp:123: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:125:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &M);
   ~~~~~^~~~~~~~~~
election_campaign.cpp:128: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
0 / 10.0

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

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	3 ms	512 KB	Output is correct
4	Correct	95 ms	23672 KB	Output is correct
5	Correct	93 ms	24776 KB	Output is correct
6	Correct	97 ms	24904 KB	Output is correct
7	Correct	93 ms	24748 KB	Output is correct
8	Correct	92 ms	24772 KB	Output is correct
9	Correct	93 ms	24904 KB	Output is correct
10	Correct	93 ms	24764 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	3 ms	512 KB	Output is correct
4	Correct	95 ms	23672 KB	Output is correct
5	Correct	93 ms	24776 KB	Output is correct
6	Correct	97 ms	24904 KB	Output is correct
7	Correct	93 ms	24748 KB	Output is correct
8	Correct	92 ms	24772 KB	Output is correct
9	Correct	93 ms	24904 KB	Output is correct
10	Correct	93 ms	24764 KB	Output is correct
11	Correct	11 ms	1920 KB	Output is correct
12	Correct	97 ms	24776 KB	Output is correct
13	Correct	105 ms	24776 KB	Output is correct
14	Correct	96 ms	24932 KB	Output is correct
15	Correct	101 ms	24752 KB	Output is correct
16	Correct	102 ms	24856 KB	Output is correct
17	Correct	101 ms	24776 KB	Output is correct
18	Correct	103 ms	24772 KB	Output is correct
19	Correct	105 ms	24776 KB	Output is correct
20	Correct	104 ms	24772 KB	Output is correct