結果
問題 | No.1194 Replace |
ユーザー | uzzy |
提出日時 | 2020-08-22 18:24:34 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,570 ms / 2,000 ms |
コード長 | 2,115 bytes |
コンパイル時間 | 2,436 ms |
コンパイル使用メモリ | 205,728 KB |
実行使用メモリ | 114,188 KB |
最終ジャッジ日時 | 2024-04-27 03:26:00 |
合計ジャッジ時間 | 25,604 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 952 ms
84,388 KB |
testcase_01 | AC | 1,070 ms
87,872 KB |
testcase_02 | AC | 794 ms
77,896 KB |
testcase_03 | AC | 661 ms
70,992 KB |
testcase_04 | AC | 1,091 ms
87,560 KB |
testcase_05 | AC | 935 ms
84,348 KB |
testcase_06 | AC | 876 ms
80,964 KB |
testcase_07 | AC | 1,570 ms
114,188 KB |
testcase_08 | AC | 1,545 ms
114,100 KB |
testcase_09 | AC | 1,561 ms
114,032 KB |
testcase_10 | AC | 1,534 ms
114,104 KB |
testcase_11 | AC | 1,534 ms
114,136 KB |
testcase_12 | AC | 1,521 ms
114,140 KB |
testcase_13 | AC | 765 ms
62,664 KB |
testcase_14 | AC | 649 ms
57,480 KB |
testcase_15 | AC | 571 ms
60,208 KB |
testcase_16 | AC | 812 ms
63,216 KB |
testcase_17 | AC | 508 ms
56,748 KB |
testcase_18 | AC | 507 ms
53,920 KB |
testcase_19 | AC | 768 ms
64,820 KB |
testcase_20 | AC | 13 ms
32,068 KB |
testcase_21 | AC | 10 ms
32,196 KB |
testcase_22 | AC | 11 ms
32,196 KB |
testcase_23 | AC | 197 ms
44,424 KB |
testcase_24 | AC | 71 ms
39,616 KB |
testcase_25 | AC | 30 ms
33,424 KB |
testcase_26 | AC | 231 ms
43,972 KB |
testcase_27 | AC | 41 ms
33,904 KB |
testcase_28 | AC | 101 ms
37,056 KB |
testcase_29 | AC | 21 ms
35,140 KB |
ソースコード
#pragma GCC optimize ("O2") #pragma GCC target ("avx2") #include<bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, n) for(int i = 0; i < (n); i++) #define rep1(i, n) for(int i = 1; i <= (n); i++) #define co(x) cout << (x) << "\n" #define cosp(x) cout << (x) << " " #define ce(x) cerr << (x) << "\n" #define cesp(x) cerr << (x) << " " #define pb push_back #define mp make_pair #define chmin(x, y) x = min(x, y) #define chmax(x, y) x = max(x, y) #define Would #define you #define please int N, M; const int NV = 400001; int KL[400001]; vector<int> E[NV], E2[NV]; vector<int> ba, E3[NV]; set<int> vis; map<int, int> S; int kazu[NV], memo[NV]; int NS; int zaatu(int A) { return lower_bound(KL, KL + M + M, A) - KL; } void dfs1(int a) { int A = zaatu(a); if (vis.find(A) == vis.end()) { vis.insert(A); for (int i : E[A]) dfs1(KL[i]); ba.pb(a); } } void dfs2(int a) { int A = zaatu(a); if (!S[A]) { S[A] = NS; chmax(kazu[NS], a); for (int i : E2[A]) dfs2(KL[i]); } } int dfs3(int A) { if (memo[A]) return memo[A]; int ret = kazu[A]; for (int i : E3[A]) chmax(ret, dfs3(i)); return memo[A] = ret; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> M; set<int> list; int kl = 0; int U[200000], V[200000]; rep(i, M) { int u, v; cin >> u >> v; U[i] = u; V[i] = v; KL[kl++] = u; KL[kl++] = v; list.insert(u); list.insert(v); } sort(KL, KL + M + M); rep(i, M) { int u = zaatu(U[i]); int v = zaatu(V[i]); E[u].pb(v); E2[v].pb(u); } for(auto i : list) { dfs1(i); } int m = ba.size(); for (int i = m - 1; i >= 0; i--) if (S[zaatu(ba[i])] == 0) { NS++; dfs2(ba[i]); } for (auto P : list) { int p = zaatu(P); for (int j : E[p]) { if (S[p] != S[j]) E3[S[p]].pb(S[j]); } } //rep1(i, N) { // cesp(i); // int j = zaatu(i); // cesp(j); // ce(S[j]); // for (auto k : E3[S[j]]) { // cesp(k); // }ce(""); //} ll kotae = 0; for (auto i : list) { kotae -= i; int tmp = zaatu(i); int j = S[tmp]; kotae += dfs3(j); } kotae += ll(N) * (N + 1) / 2; co(kotae); Would you please return 0; }