Submission #201275

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
201275	2020-02-10T05:52:16 Z	quocnguyen1012	Election Campaign (JOI15_election_campaign)	C++14	10 / 100	196 ms	31864 KB

election_campaign

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 5;

int U[maxn], V[maxn], W[maxn];
vector<int> have[maxn];
int N, M, depth[maxn], par[maxn][20];
vector<int> adj[maxn];
ll f[maxn], sum[maxn];
int tin[maxn], tout[maxn];

void prepare(int u, int p = -1)
{
  static int nTime = 0;
  tin[u] = ++nTime;
  for (int i = 1; (1 << i) <= N; ++i){
    par[u][i] = par[par[u][i - 1]][i - 1];
  }
  for (int v : adj[u]){
    if (v == p) continue;
    depth[v] = depth[u] + 1;
    par[v][0] = u;
    prepare(v, u);
  }
  tout[u] = nTime;
}

bool In(int u, int v)
{
  return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int LCA(int x, int y)
{
  if (depth[y] > depth[x]) swap(x, y);
  if (In(y, x)) return y;
  for (int k = 19; k >= 0; --k){
    if (depth[par[x][k]] >= depth[y]){
      x = par[x][k];
    }
  }
  if (x == y) return x;
  for (int k = 19; k >= 0; --k){
    if (par[x][k] != par[y][k]){
      x = par[x][k];
      y = par[y][k];
    }
  }
  return par[x][0];
}

int Can(int u, int v)
{
  int l = (u == 1 ? 0 : 1), r = adj[u].size() - 1;
  while (l <= r){
    int mid = (l + r) / 2;
    int p = adj[u][mid];
    if (tout[p] < tin[v])
      l = mid + 1;
    else
      r = mid - 1;
  }
  return adj[u][l];
}

void solve(int u, int p = -1)
{
  for (int v : adj[u]){
    if (v == p) continue;
    solve(v, u);
    sum[u] += f[v];
  }
  f[u] = sum[u];
  //cerr << u << ' ' << sum[u] << '\n';
  for (auto & i : have[u]){
    if (U[i] != u) swap(U[i], V[i]);
    if (U[i] == u){
      f[u] = max(f[u], sum[u] + W[i] + sum[V[i]] - f[Can(u, V[i])]);
    }
    else{
      f[u] = max(f[u], sum[u] + W[i] + sum[U[i]] + sum[V[i]] - f[Can(u, U[i])] - f[Can(u, V[i])]);
    }
  }
  ///cerr << u << ' ' << f[u] << '\n';
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N;
  for (int i = 1; i < N; ++i){
    int u, v; cin >> u >> v;
    adj[u].pb(v); adj[v].pb(u);
  }
  cin >> M;
  for (int i = 1; i <= M; ++i){
    cin >> U[i] >> V[i] >> W[i];
  }
  depth[1] = 1;
  prepare(1);
  for (int i = 1; i <= M; ++i){
    have[LCA(U[i], V[i])].pb(i);
  }
  for (int i = 1; i <= N; ++i){
    sort(adj[i].begin(), adj[i].end(), [&](const int & x, const int & y){
      return tin[x] < tin[y];
    });
  }
  solve(1);
  cout << f[1];
}

Compilation message

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:99:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:100:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	5112 KB	Output is correct
2	Correct	9 ms	5112 KB	Output is correct
3	Correct	9 ms	5240 KB	Output is correct
4	Correct	111 ms	31224 KB	Output is correct
5	Correct	103 ms	31352 KB	Output is correct
6	Correct	105 ms	31356 KB	Output is correct
7	Correct	110 ms	31224 KB	Output is correct
8	Correct	109 ms	31408 KB	Output is correct
9	Correct	108 ms	31352 KB	Output is correct
10	Correct	109 ms	31352 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	5112 KB	Output is correct
2	Correct	9 ms	5112 KB	Output is correct
3	Correct	9 ms	5240 KB	Output is correct
4	Correct	111 ms	31224 KB	Output is correct
5	Correct	103 ms	31352 KB	Output is correct
6	Correct	105 ms	31356 KB	Output is correct
7	Correct	110 ms	31224 KB	Output is correct
8	Correct	109 ms	31408 KB	Output is correct
9	Correct	108 ms	31352 KB	Output is correct
10	Correct	109 ms	31352 KB	Output is correct
11	Correct	16 ms	6136 KB	Output is correct
12	Correct	108 ms	31556 KB	Output is correct
13	Correct	109 ms	31608 KB	Output is correct
14	Correct	103 ms	31740 KB	Output is correct
15	Correct	104 ms	31608 KB	Output is correct
16	Correct	105 ms	31640 KB	Output is correct
17	Correct	112 ms	31864 KB	Output is correct
18	Correct	112 ms	31608 KB	Output is correct
19	Correct	105 ms	31608 KB	Output is correct
20	Correct	111 ms	31520 KB	Output is correct