結果
問題 | No.2311 [Cherry 5th Tune] Cherry Month |
ユーザー | square1001 |
提出日時 | 2023-03-25 12:43:42 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 7,896 bytes |
コンパイル時間 | 2,518 ms |
コンパイル使用メモリ | 133,472 KB |
実行使用メモリ | 814,620 KB |
最終ジャッジ日時 | 2024-12-15 19:03:28 |
合計ジャッジ時間 | 23,855 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 240 ms
51,288 KB |
testcase_03 | AC | 116 ms
27,504 KB |
testcase_04 | AC | 111 ms
22,540 KB |
testcase_05 | AC | 107 ms
22,344 KB |
testcase_06 | AC | 134 ms
26,428 KB |
testcase_07 | AC | 112 ms
24,028 KB |
testcase_08 | AC | 191 ms
47,416 KB |
testcase_09 | AC | 171 ms
38,148 KB |
testcase_10 | AC | 153 ms
34,560 KB |
testcase_11 | AC | 170 ms
40,900 KB |
testcase_12 | AC | 213 ms
45,212 KB |
testcase_13 | AC | 210 ms
46,608 KB |
testcase_14 | AC | 205 ms
47,048 KB |
testcase_15 | AC | 219 ms
48,140 KB |
testcase_16 | AC | 134 ms
27,424 KB |
testcase_17 | AC | 221 ms
47,152 KB |
testcase_18 | AC | 199 ms
43,828 KB |
testcase_19 | AC | 214 ms
48,496 KB |
testcase_20 | AC | 205 ms
47,512 KB |
testcase_21 | AC | 178 ms
35,220 KB |
testcase_22 | AC | 183 ms
35,248 KB |
testcase_23 | AC | 205 ms
50,040 KB |
testcase_24 | AC | 203 ms
48,500 KB |
testcase_25 | AC | 211 ms
40,728 KB |
testcase_26 | AC | 252 ms
52,444 KB |
testcase_27 | AC | 263 ms
73,924 KB |
testcase_28 | AC | 261 ms
73,864 KB |
testcase_29 | AC | 271 ms
73,896 KB |
testcase_30 | MLE | - |
testcase_31 | MLE | - |
testcase_32 | MLE | - |
testcase_33 | AC | 233 ms
56,552 KB |
testcase_34 | AC | 220 ms
56,396 KB |
testcase_35 | AC | 221 ms
56,444 KB |
testcase_36 | AC | 270 ms
59,160 KB |
testcase_37 | AC | 279 ms
59,276 KB |
testcase_38 | AC | 281 ms
58,816 KB |
testcase_39 | AC | 283 ms
58,852 KB |
testcase_40 | AC | 274 ms
58,568 KB |
testcase_41 | AC | 292 ms
59,092 KB |
testcase_42 | AC | 270 ms
58,136 KB |
testcase_43 | AC | 289 ms
59,356 KB |
testcase_44 | AC | 271 ms
60,172 KB |
testcase_45 | AC | 263 ms
60,284 KB |
testcase_46 | AC | 196 ms
51,336 KB |
testcase_47 | AC | 500 ms
60,336 KB |
testcase_48 | AC | 269 ms
59,032 KB |
testcase_49 | AC | 268 ms
58,584 KB |
testcase_50 | AC | 260 ms
58,768 KB |
ソースコード
#include <vector> #include <iostream> #include <algorithm> using namespace std; class query { public: int tp, t, x, y; query() : tp(-1), t(-1), x(-1), y(-1) {} query(int tp_, int t_, int x_, int y_) : tp(tp_), t(t_), x(x_), y(y_) {} bool operator<(const query& q) const { return t < q.t; } }; vector<long long> solve(int N, int M, int Q, const vector<long long>& TA, const vector<int>& TP, const vector<int>& X, const vector<int>& Y, const vector<int>& S, const vector<int>& I) { // step #1. preparation vector<query> qs(M + Q); for (int i = 0; i < M; i++) { qs[i] = query(TP[i], i * 2 + 1, X[i], Y[i]); } for (int i = 0; i < Q; i++) { qs[M + i] = query(5, S[i] * 2, I[i], i); } sort(qs.begin(), qs.end()); // step #2. renumber vertices vector<vector<int> > group(N); vector<int> root(N), id(N), sz(N); for (int i = 0; i < N; i++) { group[i] = { i }; root[i] = i; id[i] = 0; sz[i] = 1; } for (query q : qs) { if (q.tp == 1) { int rx = root[q.x]; int ry = root[q.y]; if (rx != ry) { if (group[rx].size() < group[ry].size()) { swap(rx, ry); } group[rx].insert(group[rx].end(), group[ry].begin(), group[ry].end()); for (int j : group[ry]) { id[j] += sz[rx]; } sz[rx] += sz[ry]; for (int j : group[ry]) { root[j] = rx; } group[ry].clear(); } } } int offset = 0; for (int i = 0; i < N; i++) { for (int j : group[i]) { id[j] += offset; } offset += group[i].size(); } for (query &q : qs) { if (q.tp == 1) { q.x = id[q.x]; q.y = id[q.y]; } else { q.x = id[q.x]; } } vector<long long> A(N); for (int i = 0; i < N; i++) { A[id[i]] = TA[i]; } // step #3. find left/right of update queries vector<int> idl(N), idr(N); for (int i = 0; i < N; i++) { group[i] = { i }; root[i] = i; idl[i] = i; idr[i] = i + 1; } vector<int> l(M + Q, -1), r(M + Q, -1); for (int i = 0; i < M + Q; i++) { query q = qs[i]; if (q.tp == 1) { int rx = root[q.x]; int ry = root[q.y]; if (rx != ry) { if (group[rx].size() < group[ry].size()) { swap(rx, ry); } group[rx].insert(group[rx].end(), group[ry].begin(), group[ry].end()); idl[rx] = min(idl[rx], idl[ry]); idr[rx] = max(idr[rx], idr[ry]); for (int j : group[ry]) { root[j] = rx; } } } if (q.tp == 4) { l[i] = idl[root[q.x]]; r[i] = idr[root[q.x]]; } } // step #4. find all high-degree vertices vector<int> deg(N, 0); for (query q : qs) { if (q.tp == 1) { deg[q.x] += 1; deg[q.y] += 1; } } int Z = 0; vector<int> vert_id(N, -1); for (int i = 0; i < N; i++) { if (1LL * deg[i] * deg[i] >= 100 * N) { vert_id[i] = Z; Z += 1; } } vector<vector<int> > flag(N, vector<int>(Z, -1)); // step #5. binary indexed tree vector<long long> bit(N + 1); auto add = [&](int pos, int val) { for (int i = pos + 1; i <= N; i += i & (-i)) { bit[i] += val; } }; auto getsum = [&](int pos) { long long answer = 0; for (int i = pos; i >= 1; i -= i & (-i)) { answer += bit[i]; } return answer; }; // step #6. process queries vector<vector<int> > g(N); vector<long long> val(N, 0), answer(Q, -1); vector<vector<long long> > bigval(M + Q + 1); bigval[0] = vector<long long>(Z, 0); for (int i = 0; i < M + Q; i++) { bigval[i + 1] = bigval[i]; query q = qs[i]; if (q.tp == 1) { if (vert_id[q.x] == -1) { g[q.x].push_back(q.y); } else if (flag[q.y][vert_id[q.x]] == -1) { flag[q.y][vert_id[q.x]] = i; } if (vert_id[q.y] == -1) { g[q.y].push_back(q.x); } else if (flag[q.x][vert_id[q.y]] == -1) { flag[q.x][vert_id[q.y]] = i; } } if (q.tp == 2) { val[q.x] += q.y; } if (q.tp == 3) { if (vert_id[q.x] == -1) { for (int j : g[q.x]) { val[j] += q.y; } } else { bigval[i + 1][vert_id[q.x]] += q.y; } val[q.x] += q.y; } if (q.tp == 4) { add(l[i], q.y); add(r[i], -q.y); } if (q.tp == 5) { long long subval = val[q.x]; for (int j = 0; j < Z; j++) { if (flag[q.x][j] != -1) { subval += bigval[i + 1][j] - bigval[flag[q.x][j]][j]; } } subval += getsum(q.x + 1); answer[q.y] = max(A[q.x] - subval, 0LL); } } return answer; } vector<long long> solve_easy(int N, int M, int Q, const vector<long long>& TA, const vector<int>& TP, const vector<int>& X, const vector<int>& Y, const vector<int>& S, const vector<int>& I) { // step #1. preparation vector<query> qs(M + Q); for (int i = 0; i < M; i++) { qs[i] = query(TP[i], i * 2 + 1, X[i], Y[i]); } for (int i = 0; i < Q; i++) { qs[M + i] = query(5, S[i] * 2, I[i], i); } sort(qs.begin(), qs.end()); // step #2. renumber vertices vector<long long> A = TA; vector<long long> answer(Q, -1); vector<vector<int> > g(N); for (query q : qs) { if (q.tp == 1) { g[q.x].push_back(q.y); g[q.y].push_back(q.x); } if (q.tp == 2) { A[q.x] = max(A[q.x] - q.y, 0LL); } if (q.tp == 3) { A[q.x] = max(A[q.x] - q.y, 0LL); for (int i : g[q.x]) { A[i] = max(A[i] - q.y, 0LL); } } if (q.tp == 4) { vector<bool> vis(N, false); auto dfs = [&](auto& self, int pos) -> void { vis[pos] = true; A[pos] = max(A[pos] - q.y, 0LL); for (int i : g[pos]) { if (!vis[i]) { self(self, i); } } }; dfs(dfs, q.x); } if (q.tp == 5) { answer[q.y] = A[q.x]; } } return answer; } #include <set> #include <random> #include <string> mt19937_64 mt(1); int rand_int(int l, int r) { return l + int(mt() % (r - l)); } template<class T> string to_string(const vector<T>& arr) { string res = "["; for (int i = 0; i < int(arr.size()); i++) { if (i != 0) { res += ", "; } res += std::to_string(arr[i]); } res += "]"; return res; } bool checker(int N) { const int samples = 10000; for (int id = 1; id <= samples; id++) { vector<long long> A(N); for (int i = 0; i < N; i++) { A[i] = 99; } int M = 2 * N; set<pair<int, int> > s; vector<int> TP(M), X(M), Y(M); for (int i = 0; i < M; i++) { TP[i] = rand_int(s.size() != N * (N - 1) / 2 ? 1 : 2, 5); X[i] = rand_int(0, N); if (TP[i] == 1) { do { X[i] = rand_int(0, N); Y[i] = rand_int(0, N); } while (X[i] == Y[i] || s.find(make_pair(min(X[i], Y[i]), max(X[i], Y[i]))) != s.end()); s.insert(make_pair(min(X[i], Y[i]), max(X[i], Y[i]))); } else { X[i] = rand_int(0, N); Y[i] = rand_int(1, 10); } } int Q = 1; vector<int> S(Q), I(Q); for (int i = 0; i < Q; i++) { S[i] = rand_int(0, M + 1); I[i] = rand_int(0, N); } vector<long long> res1 = solve(N, M, Q, A, TP, X, Y, S, I); vector<long long> res2 = solve_easy(N, M, Q, A, TP, X, Y, S, I); if (res1 != res2) { cout << "N = " << N << ", M = " << M << ", Q = " << Q << ", Case #" << id << ":" << endl; cout << "A = " << to_string(A) << endl; cout << "TP= " << to_string(TP) << endl; cout << "X = " << to_string(X) << endl; cout << "Y = " << to_string(Y) << endl; cout << "S = " << to_string(S) << endl; cout << "I = " << to_string(I) << endl; cout << "Returns: " << to_string(res1) << endl; cout << "Answer: " << to_string(res2) << endl; return false; } } return true; } int main() { /* for (int N = 2; N <= 10; N++) { if (!checker(N)) { break; } cout << "N = " << N << " Complete!" << endl; } */ cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; vector<long long> A(N); for (int i = 0; i < N; i++) { cin >> A[i]; } int M; cin >> M; vector<int> TP(M), X(M), Y(M); for (int i = 0; i < M; i++) { cin >> TP[i] >> X[i] >> Y[i]; X[i] -= 1; Y[i] -= (TP[i] == 1 ? 1 : 0); } int Q; cin >> Q; vector<int> S(Q), I(Q); for (int i = 0; i < Q; i++) { cin >> S[i] >> I[i]; I[i] -= 1; } vector<long long> answer = solve(N, M, Q, A, TP, X, Y, S, I); for (int i = 0; i < Q; i++) { cout << answer[i] << '\n'; } return 0; }