結果
問題 | No.1194 Replace |
ユーザー | Series_205 |
提出日時 | 2020-08-22 15:54:35 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,078 ms / 2,000 ms |
コード長 | 3,281 bytes |
コンパイル時間 | 2,217 ms |
コンパイル使用メモリ | 217,080 KB |
実行使用メモリ | 51,964 KB |
最終ジャッジ日時 | 2023-08-05 12:57:45 |
合計ジャッジ時間 | 19,300 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 674 ms
34,328 KB |
testcase_01 | AC | 757 ms
36,184 KB |
testcase_02 | AC | 567 ms
30,156 KB |
testcase_03 | AC | 438 ms
26,240 KB |
testcase_04 | AC | 747 ms
36,192 KB |
testcase_05 | AC | 662 ms
34,020 KB |
testcase_06 | AC | 603 ms
32,060 KB |
testcase_07 | AC | 1,046 ms
51,752 KB |
testcase_08 | AC | 1,042 ms
51,764 KB |
testcase_09 | AC | 1,058 ms
51,804 KB |
testcase_10 | AC | 1,078 ms
51,844 KB |
testcase_11 | AC | 1,054 ms
51,756 KB |
testcase_12 | AC | 1,040 ms
51,964 KB |
testcase_13 | AC | 579 ms
21,608 KB |
testcase_14 | AC | 468 ms
18,320 KB |
testcase_15 | AC | 397 ms
20,116 KB |
testcase_16 | AC | 560 ms
21,800 KB |
testcase_17 | AC | 354 ms
18,496 KB |
testcase_18 | AC | 362 ms
16,404 KB |
testcase_19 | AC | 556 ms
22,752 KB |
testcase_20 | AC | 2 ms
4,380 KB |
testcase_21 | AC | 2 ms
4,376 KB |
testcase_22 | AC | 2 ms
4,376 KB |
testcase_23 | AC | 126 ms
10,984 KB |
testcase_24 | AC | 33 ms
6,632 KB |
testcase_25 | AC | 12 ms
4,380 KB |
testcase_26 | AC | 148 ms
9,312 KB |
testcase_27 | AC | 17 ms
4,376 KB |
testcase_28 | AC | 57 ms
6,504 KB |
testcase_29 | AC | 6 ms
4,380 KB |
ソースコード
#include <bits/stdc++.h> #define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++) #define FORR(i, n) for(ll i = (ll)n - 1LL; i >= 0LL; i--) #define rep(i, n) FOR(i, 0, n) #define ALL(x) begin(x), end(x) using namespace std; using ll = long long; constexpr ll Mod = 998244353; constexpr ll mod = 1e9 + 7; constexpr ll inf = 1LL << 60; const double PI = acos(-1); template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } /*-------------------------------------------*/ template <int M> class ModInt { int x; public: constexpr ModInt() : x(0) {} constexpr ModInt(int64_t y) : x(y >= 0 ? y % M : (M - (-y) % M) % M) {} constexpr ModInt &operator+=(const ModInt p) { if((x += p.x) >= M) x -= M; return *this; } constexpr ModInt &operator-=(const ModInt p) { if((x += M - p.x) >= M) x -= M; return *this; } constexpr ModInt &operator*=(const ModInt p) { x = (int)(1LL * x * p.x % M); return *this; } constexpr ModInt &operator/=(const ModInt p) { *this *= p.inverse(); return *this; } constexpr ModInt operator-() const { return ModInt(-x); } constexpr ModInt operator+(const ModInt p) const { return ModInt(*this) += p; } constexpr ModInt operator-(const ModInt p) const { return ModInt(*this) -= p; } constexpr ModInt operator*(const ModInt p) const { return ModInt(*this) *= p; } constexpr ModInt operator/(const ModInt p) const { return ModInt(*this) /= p; } constexpr bool operator==(const ModInt p) const { return x == p.x; } constexpr bool operator!=(const ModInt p) const { return x != p.x; } constexpr ModInt inverse() const { int a = x, b = M, u = 1, v = 0, t = 0; while(b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return ModInt(u); } constexpr ModInt pow(int64_t k) const { ModInt ret(1), mul(x); while(k > 0) { if(k & 1) ret *= mul; mul *= mul; k >>= 1; } return ret; } constexpr friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; } constexpr friend istream &operator>>(istream &is, ModInt &a) { int64_t t = 0; is >> t; a = ModInt(t); return (is); } }; using mint = ModInt<Mod>; int n, m; map<int, vector<int>, greater<int>> G; map<int, int> d; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cin >> n >> m; rep(i, m) { int b, c; cin >> b >> c; G[c].push_back(b); d[c] = c; d[b] = b; } ll ans = 1LL * n * (n + 1) / 2; queue<int> que; for(auto [v, vec] : G) { if(d[v] != v) continue; que.push(v); while(!que.empty()) { int u = que.front(); que.pop(); for(auto w : G[u]) if(chmax(d[w], v)) que.push(w); } } for(auto [key, val] : d) ans += val - key; cout << ans << endl; return 0; }