結果
問題 | No.2311 [Cherry 5th Tune] Cherry Month |
ユーザー | square1001 |
提出日時 | 2023-03-25 12:42:18 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 7,890 bytes |
コンパイル時間 | 2,263 ms |
コンパイル使用メモリ | 132,384 KB |
実行使用メモリ | 814,692 KB |
最終ジャッジ日時 | 2024-12-15 19:02:38 |
合計ジャッジ時間 | 24,151 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 242 ms
51,332 KB |
testcase_03 | AC | 113 ms
27,464 KB |
testcase_04 | AC | 110 ms
22,504 KB |
testcase_05 | AC | 109 ms
22,416 KB |
testcase_06 | AC | 136 ms
26,588 KB |
testcase_07 | AC | 115 ms
24,108 KB |
testcase_08 | AC | 207 ms
47,444 KB |
testcase_09 | AC | 193 ms
38,296 KB |
testcase_10 | AC | 163 ms
34,648 KB |
testcase_11 | AC | 177 ms
40,968 KB |
testcase_12 | AC | 237 ms
45,156 KB |
testcase_13 | AC | 206 ms
46,516 KB |
testcase_14 | AC | 213 ms
47,160 KB |
testcase_15 | AC | 220 ms
48,128 KB |
testcase_16 | AC | 144 ms
27,424 KB |
testcase_17 | AC | 225 ms
47,168 KB |
testcase_18 | AC | 201 ms
43,844 KB |
testcase_19 | AC | 230 ms
48,404 KB |
testcase_20 | AC | 221 ms
47,420 KB |
testcase_21 | AC | 189 ms
35,144 KB |
testcase_22 | AC | 183 ms
35,160 KB |
testcase_23 | AC | 211 ms
50,060 KB |
testcase_24 | AC | 204 ms
48,480 KB |
testcase_25 | AC | 204 ms
40,840 KB |
testcase_26 | AC | 241 ms
52,560 KB |
testcase_27 | AC | 281 ms
73,948 KB |
testcase_28 | AC | 277 ms
73,996 KB |
testcase_29 | AC | 282 ms
73,952 KB |
testcase_30 | MLE | - |
testcase_31 | MLE | - |
testcase_32 | MLE | - |
testcase_33 | AC | 239 ms
56,412 KB |
testcase_34 | AC | 221 ms
56,368 KB |
testcase_35 | AC | 224 ms
56,448 KB |
testcase_36 | AC | 274 ms
59,168 KB |
testcase_37 | AC | 279 ms
59,240 KB |
testcase_38 | AC | 273 ms
58,984 KB |
testcase_39 | AC | 281 ms
58,776 KB |
testcase_40 | AC | 265 ms
58,536 KB |
testcase_41 | AC | 284 ms
59,028 KB |
testcase_42 | AC | 263 ms
58,248 KB |
testcase_43 | AC | 284 ms
59,468 KB |
testcase_44 | AC | 256 ms
60,408 KB |
testcase_45 | AC | 258 ms
60,248 KB |
testcase_46 | AC | 208 ms
51,484 KB |
testcase_47 | AC | 530 ms
60,368 KB |
testcase_48 | AC | 259 ms
59,020 KB |
testcase_49 | AC | 293 ms
58,620 KB |
testcase_50 | AC | 331 ms
58,700 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] >= 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; }