Submission #723531

#	Time	Username	Problem	Language	Result	Execution time	Memory
723531		quiet_space	Toll (APIO13_toll)	C++14	100 / 100	1074 ms	11240 KiB

toll

#include <bits/stdc++.h>
#define FOR(i,j,k) for(int i=j; i<=k; ++i)
#define ROF(i,j,k) for(int i=j; i>=k; --i)
inline int read (void) {
  int x = 0, f = 1, ch = getchar();
  while(!isdigit(ch)) { if(ch == '-') f = -f; ch = getchar(); }
  while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
  return x * f;
}
using ll = long long;
const int maxn = 100005;
const int maxm = 300005;
const int maxk = 25;
struct UFS {
  int f[maxn];
  inline void prework (int n) {
    // printf("prework n = %d\n", n);
    std::iota (f+1, f+n+1, 1);
  }
  inline int find (int x) {
    while(x != f[x]) x = f[x] = f[f[x]];
    return x;
  }
  inline bool merge (int x, int y) {
    if((x = find(x)) == (y = find(y)))
    return 0; f[x] = y; return 1;
  }
} A, B;
struct Edge {
  int x, y, w;
} e1[maxm], e2[maxk], e3[maxk];
inline bool operator < (Edge p, Edge q) {
  return p.w < q.w;
}
int id[maxn], val[maxk];
ll p[maxn];
int tot_edge, head[maxk], to[maxk<<1], link[maxk<<1];
inline void add_edge (int x, int y) {
  to[++tot_edge] = y;
  link[tot_edge] = head[x];
  head[x] = tot_edge;
}
int dep[maxn], fa[maxn];
ll sz[maxn];
void dfs (int x, int f=0) {
  dep[x] = dep[fa[x] = f] + 1; sz[x] = p[x];
  for(int now=head[x]; now; now=link[now]) {
    if(to[now] == f) continue;
    dfs (to[now], x);
    sz[x] += sz[to[now]];
  }
}
int main (void) {
  int n = read(), m = read(), k = read();
  A.prework (n); B.prework (n);
  FOR(i,1,m) {
    int x = read(), y = read(), w = read();
    e1[i] = {x, y, w};
  }
  FOR(i,1,k) {
    int x = read(), y = read();
    e2[i] = {x, y, 0}; A.merge (x, y);
  }
  std::sort(e1+1, e1+m+1);
  FOR(i,1,m) if(A.merge (e1[i].x, e1[i].y)) B.merge (e1[i].x, e1[i].y);
  int tot = 0;
  FOR(i,1,n) if(B.find(i) == i) id[i] = ++ tot;
  int rt = id[B.find(1)], cnt = 0;
  A = B;
  FOR(i,1,n) p[id[B.find(i)]] += read();
  FOR(i,1,m) if(B.merge (e1[i].x, e1[i].y)) e3[++ cnt] = e1[i];
  FOR(i,1,k) e2[i].x = id[A.find(e2[i].x)], e2[i].y = id[A.find(e2[i].y)];
  FOR(i,1,cnt) e3[i].x = id[A.find(e3[i].x)], e3[i].y = id[A.find(e3[i].y)];
  ll ans = 0;
  FOR(s,0,(1<<k)-1) {
    tot_edge = 0;
    std::fill (head+1, head+tot+1, 0);
    std::fill (val+1, val+tot+1, 1 << 30);
    A.prework (tot);
    bool flag = 0;
    FOR(i,1,k) if(s>>i-1&1)
      if(A.merge (e2[i].x, e2[i].y))
        add_edge (e2[i].x, e2[i].y), add_edge (e2[i].y, e2[i].x);
      else { flag = 1; break; }
    if(flag) continue;
    FOR(i,1,cnt)
      if(A.merge (e3[i].x, e3[i].y))
        add_edge (e3[i].x, e3[i].y), add_edge (e3[i].y, e3[i].x);
    dfs (rt);
    FOR(i,1,cnt) {
      int x = e3[i].x, y = e3[i].y, w = e3[i].w;
      while(x != y) {
        if(dep[x] < dep[y]) std::swap (x, y);
        val[x] = std::min(val[x], w); x = fa[x];
      }
    }
    ll tot = 0;
    FOR(i,1,k) if(s>>i-1&1) {
      int x = e2[i].x, y = e2[i].y;
      if(dep[x] < dep[y]) std::swap (x, y);
      tot += val[x] * sz[x];
    }
    ans = std::max(ans, tot);
  }
  printf("%lld\n", ans);
  return 0;
}

Compilation message (stderr)

toll.cpp: In member function 'bool UFS::merge(int, int)':
toll.cpp:25:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   25 |     if((x = find(x)) == (y = find(y)))
      |     ^~
toll.cpp:26:15: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   26 |     return 0; f[x] = y; return 1;
      |               ^
toll.cpp: In function 'int main()':
toll.cpp:81:23: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   81 |     FOR(i,1,k) if(s>>i-1&1)
      |                      ~^~
toll.cpp:81:18: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   81 |     FOR(i,1,k) if(s>>i-1&1)
      |                  ^
toll.cpp:98:23: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   98 |     FOR(i,1,k) if(s>>i-1&1) {
      |                      ~^~

• Subtask 1: 16 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 22 / 22
• Subtask 5: 22 / 22