QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#386436#6406. Stage ClearzlxFTHWA 2ms3832kbC++143.3kb2024-04-11 16:42:002024-04-11 16:42:01

Judging History

This is the latest submission verdict.

  • [2024-08-15 21:05:17]
  • hack成功,自动添加数据
  • (/hack/778)
  • [2024-04-11 16:42:01]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 3832kb
  • [2024-04-11 16:42:00]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)

using i64 = long long;

int n, m;

void solve1() {
  vector<i64> a(n), b(n);
  for (int i = 1; i < n; ++i) {
    cin >> a[i] >> b[i];
  }
  vector<int> from(1 << n);
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v, u--, v--;
    from[v] |= 1 << u;
  }
  vector<int> w(1 << n);
  for (int s = 0; s < (1 << n); ++s) if (s & 1) {
    for (int i = 0; i < n; ++i) {
      if (s >> i & 1) {
        w[s] += -a[i] + b[i];
      }
    }
  }
  vector<i64> f(1 << n, 1E18);
  f[1] = 0;
  for (int s = 2; s < (1 << n); ++s) if (s & 1) {
    for (int i = 1; i < n; ++i) {
      if (s >> i & 1 && from[i] & s) {
        int t = s ^ (1 << i);
        /*
          f[t] + w[t] >= a[i] -> f[t] + w[t]
          f[t] + w[t] < a[i]  -> a[i] - w[t]
        */
        if (f[t] + w[t] >= a[i]) f[s] = min(f[s], f[t]);
        else f[s] = min(f[s], a[i] - w[t]);
      }
    }
  }
  cout << f[(1 << n) - 1] << "\n";
}

void solve2() {
  vector<i64> a(n), b(n);
  for (int i = 1; i < n; ++i) {
    cin >> a[i] >> b[i];
  }
  vector<pair<int, int>> e(m);
  vector<vector<int>> adj(n);
  for (int i = 0; i < m; ++i) {
    auto &[u, v] = e[i];
    cin >> u >> v, u--, v--;
    adj[u].push_back(i);
  }
  vector<int> used(m), vis(n);
  auto dfs = [&](auto self, int u)->void {
    vis[u] = 1;
    for (auto i : adj[u]) {
      int v = e[i].second;
      if (!vis[v]) {
        self(self, v);
        used[i] = 1;
      }
    }
  };
  dfs(dfs, 0);
  vector<int> c;
  for (int i = 0; i < m; ++i) {
    if (!used[i]) {
      c.push_back(i);
    }
  }
  int cnt = c.size();
  i64 ans = 1E18;
  vector<vector<int>> adj_n(n);
  vector<int> from(n);
  auto rdfs = [&](auto self, int u)->pair<i64, i64> {
    i64 A = a[u], B = b[u];
    vector<pair<i64, i64>> d;
    for (auto i : adj_n[u]) {
      d.push_back(self(self, e[i].second));
    }
    sort(d.begin(), d.end(), [&](auto &x, auto &y) {
      if ((x.first < x.second) != (y.first < y.second)) {
        return x.first < x.second;
      }
      if (x.first < x.second) {
        return x.first < y.first;
      } else {
        return x.second > y.second;
      }
    });
    for (auto [x, y] : d) {
      if (B >= x) {
        // A - A + B - x + y
        B += -x + y;
      } else {
        // A - A + B < x 
        A = x - (-A + B);
        B = y;
      }
    }
    return {A, B};
  };
  for (int s = 0; s < (1 << cnt); ++s) {
    fill(from.begin(), from.end(), -1);
    for (int i = 0; i < n; ++i) {
      adj_n[i].clear();
    }
    for (int i = 0; i < cnt; ++i) {
      if (s >> i & 1) {
        used[c[i]] = 2;
        auto [u, v] = e[c[i]];
        if (from[v] == -1) {
          from[v] = u;
          adj_n[u].push_back(c[i]);
        }
      }
    }
    for (int i = 0; i < m; ++i) {
      if (used[i] == 1) {
        auto [u, v] = e[i];
        if (from[v] == -1) {
          from[v] = u;
          adj_n[u].push_back(i);
        }
      }
    }
    ans = min(ans, rdfs(rdfs, 0).first);
  }
  cout << ans << "\n";
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  if (n <= 26) {
    solve1();
  } else {
    solve2();
  }
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3548kb

input:

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

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 3832kb

input:

15 14
254040392438309 117083115436273
500005748229691 557255157630172
821034233718230 865199673774998
659892147898798 987564141425694
81172575487567 811635577877255
751768357864605 341103322647288
454926350150218 140191090713900
921608121471585 659295670987251
223751724062143 505619245326640
8907765...

output:

960883796054687

result:

wrong answer 1st numbers differ - expected: '1665396301509143', found: '960883796054687'