oj.uz

Submission #723531

# Submission time Handle Problem Language Result Execution time Memory
723531 2023-04-14T03:40:45 Z quiet_space Toll (APIO13_toll) C++14
100 / 100
 1074 ms 11240 KB 
#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

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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 2 ms 688 KB Output is correct
4 Correct 2 ms 724 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 2 ms 688 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 800 KB Output is correct
6 Correct 2 ms 852 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 2 ms 688 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 800 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 91 ms 11116 KB Output is correct
8 Correct 93 ms 11236 KB Output is correct
9 Correct 96 ms 11060 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 2 ms 688 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 800 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 91 ms 11116 KB Output is correct
8 Correct 93 ms 11236 KB Output is correct
9 Correct 96 ms 11060 KB Output is correct
10 Correct 732 ms 11116 KB Output is correct
11 Correct 1048 ms 11128 KB Output is correct
12 Correct 1074 ms 11240 KB Output is correct