Submission #208931

#	Time	Username	Problem	Language	Result	Execution time	Memory
208931		quocnguyen1012	Toll (APIO13_toll)	C++14	100 / 100	2135 ms	14400 KiB

toll

#include <bits/stdc++.h>

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

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> Edge;

const int maxn = 1e5 + 5;

int lab[maxn];
vector<Edge> rem, ed, mst;
vector<ii> add, adj[maxn];
int a[maxn], N, M, K, comp[maxn], cnt;
vector<int> tree[maxn];
int dep[maxn]; ii par[maxn];
ll sum[maxn], f[maxn];
int dp[maxn];

void init(int n)
{
  for(int i = 1; i <= n; ++i)
    lab[i] = -1;
}

int finds(int u)
{
  if(lab[u] < 0) return u;
  return lab[u] = finds(lab[u]);
}

bool merges(int u, int v)
{
  u = finds(u); v = finds(v);
  if(u == v) return false;
  if(lab[v] < lab[u]) swap(u, v);
  lab[u] += lab[v];
  lab[v] = u;
  return true;
}

void dfs(int u)
{
  comp[u] = cnt;
  sum[cnt] += a[u];
  for(int v : tree[u]){
    if(!comp[v]) dfs(v);
  }
}

void redfs(int u, int p = -1)
{
  f[u] = sum[u];
  for(auto v : adj[u]) if(v.fi != p){
    dep[v.fi] = dep[u] + 1;
    par[v.fi] = mp(u, v.se);
    redfs(v.fi, u);
    f[u] += f[v.fi];
  }
}

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 >> M >> K;
  for(int i = 0; i < M; ++i){
    int u, v, w; cin >> u >> v >> w;
    ed.pb(mp(w, mp(u, v)));
  }
  for(int i = 0; i < K; ++i){
    int u, v; cin >> u >> v;
    add.pb(mp(u, v));
  }
  for(int i = 1; i <= N; ++i){
    cin >> a[i];
  }

  sort(ed.begin(), ed.end());
  init(N);
  for(auto & all : ed){
    int u = all.se.fi, v = all.se.se;
    if(merges(u, v)){
      mst.pb(all);
    }
  }
  init(N);
  for(auto & all : add){
    merges(all.fi, all.se);
  }
  for(auto & all : mst){
    int u = all.se.fi, v = all.se.se;
    if(merges(u, v)){
      tree[u].pb(v); tree[v].pb(u);
    }
    else{
      rem.pb(all);
    }
  }
  for(int i = 1; i <= N; ++i){
    if(!comp[i]){
      ++cnt;
      dfs(i);
    }
  }
  ll ans = 0;
  for(int mask = 0; mask < (1 << K); ++mask){
    init(cnt);
    bool ok = true;
    for(int i = 1; i <= cnt; ++i)
      adj[i].clear();
    for(int i = 0; i < K; ++i){
      if(mask >> i & 1){
        int u = comp[add[i].fi], v = comp[add[i].se];
        if(!merges(u, v)){
          ok = false;
          break;
        }
        dp[i + 1] = 1e9;
        adj[u].eb(v, i + 1); adj[v].eb(u, i + 1);
      }
    }
    if(ok == false) break;
    vector<Edge> tmp;
    for(auto & all : rem){
      int u = comp[all.se.fi], v = comp[all.se.se];
      if(merges(u, v)){
        adj[u].eb(v, 0);
        adj[v].eb(u, 0);
      }
      else{
        tmp.pb(all);
      }
    }
    dep[1] = 1;
    redfs(1, 1);
    for(auto & all : tmp){
      int u = comp[all.se.fi], v = comp[all.se.se], w = all.fi;
      if(dep[u] > dep[v]) swap(u, v);
			while(dep[u] < dep[v]){
				if(par[v].se != 0) dp[par[v].se] = min(dp[par[v].se], w);
				v = par[v].fi;
			}
			while(u != v){
				if(par[v].se != 0) dp[par[v].se] = min(dp[par[v].se], w);
				if(par[u].se != 0) dp[par[u].se] = min(dp[par[u].se], w);
				v = par[v].fi;
				u = par[u].fi;
			}
    }
    ll res = 0;
    for(int i = 0; i < K; ++i){
      if(mask >> i & 1){
        int u = add[i].fi, v = add[i].se;
        u = comp[u]; v = comp[v];
        if(dep[v] > dep[u]) swap(u, v);
        res += 1ll * dp[i + 1] * f[u];
      }
    }
    ans = max(ans, res);
  }
  cout << ans;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:71: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);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
toll.cpp:72: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: 16 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 22 / 22
• Subtask 5: 22 / 22