結果
問題 | No.2523 Trick Flower |
ユーザー | 👑 hos.lyric |
提出日時 | 2023-10-27 22:01:43 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 367 ms / 4,000 ms |
コード長 | 3,538 bytes |
コンパイル時間 | 1,327 ms |
コンパイル使用メモリ | 125,016 KB |
実行使用メモリ | 16,560 KB |
最終ジャッジ日時 | 2023-10-27 22:01:49 |
合計ジャッジ時間 | 4,913 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 1 ms
4,348 KB |
testcase_03 | AC | 2 ms
4,348 KB |
testcase_04 | AC | 2 ms
4,348 KB |
testcase_05 | AC | 2 ms
4,348 KB |
testcase_06 | AC | 1 ms
4,348 KB |
testcase_07 | AC | 1 ms
4,348 KB |
testcase_08 | AC | 2 ms
4,348 KB |
testcase_09 | AC | 2 ms
4,348 KB |
testcase_10 | AC | 2 ms
4,348 KB |
testcase_11 | AC | 2 ms
4,348 KB |
testcase_12 | AC | 2 ms
4,348 KB |
testcase_13 | AC | 2 ms
4,348 KB |
testcase_14 | AC | 2 ms
4,348 KB |
testcase_15 | AC | 367 ms
16,560 KB |
testcase_16 | AC | 316 ms
16,560 KB |
testcase_17 | AC | 40 ms
9,628 KB |
testcase_18 | AC | 49 ms
14,584 KB |
testcase_19 | AC | 127 ms
11,208 KB |
testcase_20 | AC | 120 ms
11,208 KB |
testcase_21 | AC | 122 ms
11,208 KB |
testcase_22 | AC | 135 ms
11,208 KB |
testcase_23 | AC | 127 ms
11,208 KB |
testcase_24 | AC | 63 ms
7,844 KB |
testcase_25 | AC | 91 ms
10,484 KB |
testcase_26 | AC | 91 ms
9,956 KB |
testcase_27 | AC | 96 ms
10,748 KB |
testcase_28 | AC | 83 ms
9,428 KB |
testcase_29 | AC | 17 ms
5,084 KB |
testcase_30 | AC | 77 ms
8,900 KB |
testcase_31 | AC | 5 ms
4,348 KB |
testcase_32 | AC | 45 ms
6,552 KB |
testcase_33 | AC | 106 ms
11,012 KB |
ソースコード
#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") struct Functional { int n; vector<int> par; int cyclesLen; vector<vector<int>> cycles; // cycle id or -1 vector<int> on; // tree vector<vector<int>> graph; // root vector<int> rs; Functional() {} Functional(const vector<int> &par_) : par(par_) { n = par.size(); cycles.clear(); vector<int> vis(n, -1); for (int s = 0; s < n; ++s) { int u = s; for (; !~vis[u]; u = par[u]) { vis[u] = s; } if (vis[u] == s) { vector<int> cycle; for (int v = u; ; ) { cycle.push_back(v); if ((v = par[v]) == u) break; } cycles.push_back(cycle); } } cyclesLen = cycles.size(); on.assign(n, -1); for (int k = 0; k < cyclesLen; ++k) { for (const int u : cycles[k]) { on[u] = k; } } graph.assign(n, {}); for (int u = 0; u < n; ++u) if (!~on[u]) { graph[par[u]].push_back(u); } rs.assign(n, -1); for (int u = 0; u < n; ++u) if (~on[u]) { dfs(u, u); } } void dfs(int u, int r) { rs[u] = r; for (const int v : graph[u]) { dfs(v, r); } } }; int N; vector<Int> A, B; vector<int> C; Functional F; Int dfs(int u, Int want) { Int have = A[u]; Int need = B[u] * want; for (const int v : F.graph[u]) { need += dfs(v, want); } return max(need - have, 0LL); } bool check(Int want) { for (int k = 0; k < F.cyclesLen; ++k) { Int have = 0, need = 0; for (const int u : F.cycles[k]) { have += A[u]; need += B[u] * want; for (const int v : F.graph[u]) { need += dfs(v, want); } } if (have < need) { return false; } } return true; } int main() { for (; ~scanf("%d", &N); ) { A.resize(N); for (int u = 0; u < N; ++u) scanf("%lld", &A[u]); B.resize(N); for (int u = 0; u < N; ++u) scanf("%lld", &B[u]); C.resize(N); for (int u = 0; u < N; ++u) { scanf("%d", &C[u]); --C[u]; } F = Functional(C); Int sumA = 0, sumB = 0; for (int u = 0; u < N; ++u) sumA += A[u]; for (int u = 0; u < N; ++u) sumB += B[u]; Int lo = 0, hi = sumA / sumB + 1; for (; lo + 1 < hi; ) { const Int mid = (lo + hi) / 2; (check(mid) ? lo : hi) = mid; } printf("%lld\n", lo); } return 0; }