Submission #201293

#	Time	Username	Problem	Language	Result	Execution time	Memory
201293		quocnguyen1012	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	250 ms	31224 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];
int f[maxn], sum[maxn];
int tin[maxn], tout[maxn];

class fenwick
{
public:
  vector<int> cnt; int n;
  void init(int _n)
  {
    n = _n;
    cnt.assign(n + 5, 0);
  }
  void upd(int i, int v)
  {
    for (; i <= n; i += i & -i){
      cnt[i] += v;
    }
  }
  int get(int i)
  {
    int sum = 0;
    for (; i; i -= i & -i){
      sum += cnt[i];
    }
    return sum;
  }
}ft;

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;
  }
  assert(In(adj[u][l], v));
  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]){
    f[u] = max(f[u], sum[u] + W[i] + ft.get(tin[U[i]]) + ft.get(tin[V[i]]));
  }
  ft.upd(tin[u], sum[u] - f[u]);
  ft.upd(tout[u] + 1, f[u] - sum[u]);
  ///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; ft.init(maxn);
  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:121: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:122: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: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 30 / 30
• Subtask 5: 10 / 10
• Subtask 6: 40 / 40