Submission #201275

#	Time	Username	Problem	Language	Result	Execution time	Memory
201275		quocnguyen1012	Election Campaign (JOI15_election_campaign)	C++14	10 / 100	196 ms	31864 KiB

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 (stderr)

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
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 0 / 30
• Subtask 5: 0 / 10
• Subtask 6: 0 / 40