結果

問題 No.1194 Replace
ユーザー square1001
提出日時 2020-08-22 13:50:56
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,192 bytes
コンパイル時間 993 ms
コンパイル使用メモリ 87,668 KB
実行使用メモリ 157,628 KB
最終ジャッジ日時 2024-10-15 08:05:19
合計ジャッジ時間 7,837 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int main() {
    int N, M;
    cin >> N >> M;
    vector<int> B(M), C(M);
    for (int i = 0; i < M; ++i) {
        cin >> B[i] >> C[i];
    }
    vector<int> comp;
    for (int i = 0; i < M; ++i) {
        comp.push_back(B[i]);
        comp.push_back(C[i]);
    }
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    vector<vector<int> > G(comp.size());
    for (int i = 0; i < M; ++i) {
        int bp = lower_bound(comp.begin(), comp.end(), B[i]) - comp.begin();
        int cp = lower_bound(comp.begin(), comp.end(), C[i]) - comp.begin();
        G[bp].push_back(cp);
    }
    vector<bool> vis(comp.size(), false);
    vector<int> dp(comp.size());
    function<int(int)> dfs = [&](int pos) {
        vis[pos] = true;
        int res = pos;
        for (int i : G[pos]) {
            if (vis[i]) {
                res = max(res, dp[i]);
            }
            else {
                res = max(res, dfs(i));
            }
        }
        dp[pos] = res;
        return res;
    };
    for (int i = 0; i < comp.size(); ++i) {
        vis = vector<bool>(N, false);
        dfs(i);
    }
    long long ans = 1LL * N * (N + 1) / 2;
    for (int i = 0; i < comp.size(); ++i) {
        ans += comp[dp[i]] - comp[i];
    }
    cout << ans << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0