結果

問題 No.1194 Replace
コンテスト
ユーザー jupiro
提出日時 2020-10-22 17:05:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 425 ms / 2,000 ms
コード長 3,820 bytes
コンパイル時間 2,611 ms
コンパイル使用メモリ 145,348 KB
最終ジャッジ日時 2025-01-15 12:27:56
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>
#include <numeric>
#include <cctype>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <utility>
#include <fstream>

using namespace std;
typedef long long ll;
using ull = unsigned long long;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { a = abs(a), b = abs(b); while (b > 0) { tie(a, b) = make_pair(b, a % b); } return a; }
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

constexpr long long INF = 1LL << 60;
constexpr int inf = 1000000007;
//constexpr long long mod = 1000000007LL;
constexpr long long mod = 998244353;
constexpr int MAX = 1100000;

template<typename T>
struct Compress {
	vector<T> v;
	Compress() {}
	Compress(vector<T> _v) :v(_v) { build(); }

	void add(T x) {
		v.emplace_back(x);
	}

	void build() {
		sort(v.begin(), v.end());
		v.erase(unique(v.begin(), v.end()), v.end());
	}
	void build(vector<T> _v) {
		v = _v;
		sort(v.begin(), v.end());
		v.erase(unique(v.begin(), v.end()), v.end());
	}
	int get(T x) {
		return lower_bound(v.begin(), v.end(), x) - v.begin();
	}

	T& operator[](int i) { return v[i]; }


	int size() {
		return (int)v.size();
	}
};

struct StronglyConnectedComponents {
	int n, group_num, now_ord;
	vector<vector<int>> g;
	vector<int> low, ord, idx;
	StronglyConnectedComponents(int _n) :n(_n), low(n), ord(n, -1), idx(n), g(n), group_num(0), now_ord(0) {}
	void add_edge(int from, int to) {
		g[from].emplace_back(to);
	}
	void dfs(int cur, vector<int>& visited) {
		ord[cur] = low[cur] = now_ord++;
		visited.emplace_back(cur);
		for (auto nxt : g[cur]) {
			if (ord[nxt] == -1) {
				dfs(nxt, visited);
				chmin(low[cur], low[nxt]);
			}
			else {
				chmin(low[cur], ord[nxt]);
			}
		}
		if (ord[cur] == low[cur]) {
			while (true) {
				int v = visited.back();
				visited.pop_back();
				ord[v] = n; //別のdfs木からこないように
				idx[v] = group_num;
				if (cur == v) break;
			}
			group_num++;
		}
	}



	//sccのidxに入ってる頂点番号 idxはトポロジカル順
	void build() {
		vector<int> visited;
		for (int i = 0; i < n; i++) if (ord[i] == -1) dfs(i, visited);
		for (int i = 0; i < n; i++) idx[i] = group_num - 1 - idx[i];
	}
	//build()の後にやる
	vector<vector<int>> groups() {
		vector<vector<int>> ret(group_num);
		for (int i = 0; i < n; i++) {
			ret[idx[i]].emplace_back(i);
		}
		return ret;
	}
	int operator[](int i) { return idx[i]; }
};


int main()
{

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	ll n, m; cin >> n >> m;
	vector<pair<ll, ll>> vp(m);
	Compress<ll> comp;
	for (int i = 0; i < m; i++) {
		ll b, c; cin >> b >> c;
		vp[i] = { b,c };
		comp.add(b);
		comp.add(c);
	}
	comp.build();
	StronglyConnectedComponents scc(comp.size());
	for (auto p : vp) {
		scc.add_edge(comp.get(p.first), comp.get(p.second));
	}
	scc.build();
	auto group = scc.groups();
	vector<ll> mx(group.size());
	auto g = scc.g;
	for (int i = 0; i < group.size(); i++) {
		for (auto& e : group[i]) {
			chmax(mx[i], comp[e]);
		}
	}
	for (int i = (int)group.size() - 1; i >= 0; i--) {
		for (auto cur : group[i]) {
			for (auto nxt : g[cur]) {
				chmax(mx[i], mx[scc[nxt]]);
			}
		}
	}
	ll res = n * (n + 1) / 2;
	for (int i = 0; i < group.size(); i++) {
		for (auto& e : group[i]) {
			res += mx[i] - comp[e];
		}
	}
	cout << res << endl;
}
0