QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#401605#7077. Sheep Villagehos_lyricWA 1ms3824kbC++145.9kb2024-04-29 00:52:032024-04-29 00:52:04

Judging History

你现在查看的是最新测评结果

  • [2024-04-29 00:52:04]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3824kb
  • [2024-04-29 00:52:03]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


// cycle = (us, is), us: in increasing order of depth
struct Cactus {
  int n, m;
  vector<pair<int, int>> edges;
  vector<vector<int>> g;

  int zeit;
  vector<int> dis, fin, low, par, pari, dep;
  int cyclesLen;
  vector<pair<vector<int>, vector<int>>> cycles;

  // n + m + |cycles|
  int nn;
  vector<int> isBridge;
  vector<vector<int>> gg;

  Cactus() {}
  explicit Cactus(int n_) : n(n_), m(0), nn(0) {}
  void ae(int u, int v) {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    edges.emplace_back(u, v);
  }

  void dfs(int u, int p, int pi) {
    dis[u] = low[u] = zeit++;
    par[u] = p;
    pari[u] = pi;
    dep[u] = (!~p) ? 0 : (dep[p] + 1);
    for (const int i : g[u]) if (pi != i) {
      const int v = edges[i].first ^ edges[i].second ^ u;
      if (!~dis[v]) {
        dfs(v, u, i);
        if (low[u] > low[v]) low[u] = low[v];
      } else {
        if (low[u] > dis[v]) low[u] = dis[v];
        if (dis[u] > dis[v]) {
          vector<int> us, is;
          for (int w = u; ; w = par[w]) {
            us.push_back(w);
            if (w == v) break;
            is.push_back(pari[w]);
          }
          reverse(us.begin(), us.end());
          reverse(is.begin(), is.end());
          is.push_back(i);
          cycles.emplace_back(us, is);
        }
      }
    }
    fin[u] = zeit;
  }
  void build() {
    m = edges.size();
    g.assign(n, {});
    for (int i = 0; i < m; ++i) {
      g[edges[i].first].push_back(i);
      g[edges[i].second].push_back(i);
    }
    zeit = 0;
    dis.assign(n, -1);
    fin.assign(n, -1);
    low.assign(n, -1);
    par.assign(n, -1);
    pari.assign(n, -1);
    dep.assign(n, -1);
    cycles.clear();
    for (int u = 0; u < n; ++u) if (!~dis[u]) dfs(u, -1, -1);
    cyclesLen = cycles.size();
    nn = n + m + cyclesLen;
    isBridge.assign(m, 1);
    gg.assign(nn, {});
    for (int k = 0; k < cyclesLen; ++k) {
      for (const int u : cycles[k].first) {
        gg[u].push_back(n + m + k);
        gg[n + m + k].push_back(u);
      }
      for (const int i : cycles[k].second) {
        assert(isBridge[i]);
        isBridge[i] = 0;
      }
    }
    for (int i = 0; i < m; ++i) if (isBridge[i]) {
      gg[edges[i].first].push_back(n + i);
      gg[edges[i].second].push_back(n + i);
      gg[n + i].push_back(edges[i].first);
      gg[n + i].push_back(edges[i].second);
    }
  }
};

////////////////////////////////////////////////////////////////////////////////


int N, M, K;
vector<int> A, B;
vector<int> U, V;
vector<Int> W;

vector<int> fs;

Cactus cac;
Int ans;

int dfs(int x, int p) {
  int ret = 0;
  if (x < N) {
    // vertex
    const int u = x;
    for (const int y : cac.gg[x]) if (p != y) {
      ret += dfs(y, x);
    }
    ret += fs[u];
  } else if (x < N + M) {
    // bridge
    const int i = x - N;
    const int v = U[i] ^ V[i] ^ p;
    ret = dfs(v, x);
    ans += W[i] * abs(ret);
  } else {
    // cycle
    const int k = x - N - M;
    const auto &us = cac.cycles[k].first;
    const auto &is = cac.cycles[k].second;
    const int len = us.size();
    /*
      f: flow at us[0]
      cost = \sum[l] W[l] |f + d[l]|
    */
    vector<int> ds(len, 0);
    for (int l = 1; l < len; ++l) {
      ds[l] = ds[l - 1] + dfs(us[l], x);
    }
    Int sumW = 0;
    vector<pair<int, Int>> dws(len);
    for (int l = 0; l < len; ++l) {
      sumW += W[is[l]];
      dws[l] = make_pair(-ds[l], W[is[l]]);
    }
// cerr<<"dws = "<<dws<<endl;
    sort(dws.begin(), dws.end());
    Int nowW = 0;
    for (int j0 = 0; ; ++j0) {
      nowW += dws[j0].second;
      if (j0 && 2 * nowW >= sumW) {
        const Int f = dws[j0 - 1].first;
        Int cost = 0;
        for (int j = 0; j < len; ++j) {
          cost += dws[j].second * abs(f - dws[j].first);
        }
        ans += cost;
        break;
      }
    }
    ret = ds[len - 1];
  }
// cerr<<"[dfs] "<<x<<" "<<p<<": "<<ret<<endl;
  return ret;
}

int main() {
  for (; ~scanf("%d%d%d", &N, &M, &K); ) {
    A.resize(K); for (int k = 0; k < K; ++k) { scanf("%d", &A[k]); --A[k]; }
    B.resize(K); for (int k = 0; k < K; ++k) { scanf("%d", &B[k]); --B[k]; }
    U.resize(M);
    V.resize(M);
    W.resize(M);
    for (int i = 0; i < M; ++i) {
      scanf("%d%d%lld", &U[i], &V[i], &W[i]);
      --U[i];
      --V[i];
    }
    
    fs.assign(N, 0);
    for (const int u : A) ++fs[u];
    for (const int u : B) --fs[u];
    
    cac = Cactus(N);
    for (int i = 0; i < M; ++i) {
      cac.ae(U[i], V[i]);
    }
    cac.build();
// cerr<<"cycles = "<<cac.cycles<<", cac.gg = "<<cac.gg<<endl;
    ans = 0;
    dfs(0, -1);
    printf("%lld\n", ans);
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3780kb

input:

5 8 4
2 2 3 3
4 4 5 5
1 2 1
2 1 1
1 3 1
3 1 1
1 4 1
4 1 1
1 5 1
5 1 1

output:

8

result:

ok single line: '8'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

5 5 3
1 3 3
5 2 4
1 2 3
2 3 1
3 4 1
4 5 4
5 1 1

output:

3

result:

ok single line: '3'

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3824kb

input:

5 5 3
1 3 5
5 2 4
1 2 2
2 3 1
3 4 2
4 5 2
5 1 3

output:

6

result:

wrong answer 1st lines differ - expected: '4', found: '6'