oj.uz

답안 #975958

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
975958 2024-05-06T04:01:13 Z qwerasdfzxcl 철인 이종 경기 (APIO18_duathlon) C++17
0 / 100
 165 ms 59892 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

template<class T>
struct graph{
	using Weight_t = T;
	struct Edge_t{
		int from, to;
		T cost;
	};
	int n;
	vector<Edge_t> edge;
	vector<vector<int>> adj;
	function<bool(int)> ignore;
	graph(int n = 1): n(n), adj(n){
		assert(n >= 1);
	}
	graph(const vector<vector<int>> &adj, bool undirected = true): n((int)adj.size()), adj(n){
		assert(n >= 1);
		if(undirected){
			for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) if(u < v) link(u, v);
		}
		else for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) orient(u, v);
	}
	graph(const vector<vector<pair<int, T>>> &adj, bool undirected = true): n((int)adj.size()), adj(n){
		assert(n >= 1);
		if(undirected){
			for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) if(u < v) link(u, v, w);
		}
		else for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) orient(u, v, w);
	}
	graph(int n, vector<array<int, 2>> &edge, bool undirected = true): n(n), adj(n){
		assert(n >= 1);
		for(auto [u, v]: edge) undirected ? link(u, v) : orient(u, v);
	}
	graph(int n, vector<tuple<int, int, T>> &edge, bool undirected = true): n(n), adj(n){
		assert(n >= 1);
		for(auto [u, v, w]: edge) undirected ? link(u, v, w) : orient(u, v, w);
	}
	int operator()(int u, int id) const{
		#ifdef LOCAL
		assert(0 <= id && id < (int)edge.size());
		assert(edge[id].from == u || edge[id].to == u);
		#endif
		return u ^ edge[id].from ^ edge[id].to;
	}
	int link(int u, int v, T w = {}){ // insert an undirected edge
		int id = (int)edge.size();
		adj[u].push_back(id), adj[v].push_back(id), edge.push_back({u, v, w});
		return id;
	}
	int orient(int u, int v, T w = {}){ // insert a directed edge
		int id = (int)edge.size();
		adj[u].push_back(id), edge.push_back({u, v, w});
		return id;
	}
	void clear(){
		for(auto [u, v, w]: edge){
			adj[u].clear();
			adj[v].clear();
		}
		edge.clear();
		ignore = {};
	}
	graph transpose() const{ // the transpose of the directed graph
		graph res(n);
		for(auto id = 0; id < (int)edge.size(); ++ id){
			if(ignore && ignore(id)) continue;
			res.orient(edge[id].to, edge[id].from, edge[id].cost);
		}
		return res;
	}
	int degree(int u) const{ // the degree (outdegree if directed) of u (without the ignoration rule)
		return (int)adj[u].size();
	}
	// The adjacency list is sorted for each vertex.
	vector<vector<int>> get_adjacency_list() const{
		vector<vector<int>> res(n);
		for(auto u = 0; u < n; ++ u) for(auto id: adj[u]){
			if(ignore && ignore(id)) continue;
			res[(*this)(u, id)].push_back(u);
		}
		return res;
	}
	void set_ignoration_rule(const function<bool(int)> &f){
		ignore = f;
	}
	void reset_ignoration_rule(){
		ignore = nullptr;
	}
	friend ostream &operator<<(ostream &out, const graph &g){
		for(auto id = 0; id < (int)g.edge.size(); ++ id){
			if(g.ignore && g.ignore(id)) continue;
			auto &e = g.edge[id];
			out << "{" << e.from << ", " << e.to << ", " << e.cost << "}\n";
		}
		return out;
	}
};

// Requires graph
struct biconnected_components{
	int n, attempt, comp_attempt;
	vector<int> pos;
	vector<int> stack;
	vector<int> was;
	vector<int> comp_was;
	// block-cut tree descriptions
	vector<vector<int>> belongs; // vertex -> list of 2-vertex-connected components
	vector<vector<int>> comp_vertex; // list of vertices in a 2-vertex-connected component
	vector<vector<int>> comp_edge; // list of edges in a 2-vertex-connected component
	vector<int> bridge;
	biconnected_components(){ }
	biconnected_components(int n){ init(n); }
	template<class T>
	biconnected_components(const graph<T> &g){ init(g.n); run_all(g); }
	void init(int n){
		this->n = n;
		pos.assign(n, -1);
		was.assign(n, -2);
		attempt = -1;
		comp_was.assign(n, -2);
		comp_attempt = -1;
		belongs.assign(n, {});
		comp_vertex.clear();
		comp_edge.clear();
		bridge.clear();
	}
	// O(n + m) where n and m are the number of reachable nodes and edges respectively.
	template<class T>
	void _run(const graph<T> &g, const vector<int> &src){
		int it = 0;
		auto recurse = [&](auto self, int u, int pe)->int{
			int low = pos[u] = ++ it;
			belongs[u].clear();
			was[u] = attempt;
			for(auto id: g.adj[u]){
				if(g.ignore && g.ignore(id) || id == pe) continue;
				int v = g(u, id);
				if(was[v] != attempt){
					was[v] = attempt;
					pos[v] = 0;
				}
				if(pos[v]){
					low = min(low, pos[v]);
					if(pos[v] < pos[u]) stack.push_back(id);
				}
				else{
					int size = (int)stack.size(), up = self(self, v, id);
					low = min(low, up);
					if(up == pos[u]){
						++ comp_attempt;
						stack.push_back(id);
						vector<int> comp_v;
						vector<int> comp_e(stack.begin() + size, stack.end());
						for(auto id: comp_e){
							auto [u, v, _] = g.edge[id];
							if(comp_was[u] != comp_attempt){
								comp_was[u] = comp_attempt;
								comp_v.push_back(u);
							}
							if(comp_was[v] != comp_attempt){
								comp_was[v] = comp_attempt;
								comp_v.push_back(v);
							}
						}
						for(auto u: comp_v) belongs[u].push_back((int)comp_vertex.size());
						comp_vertex.push_back(move(comp_v));
						comp_edge.push_back(move(comp_e));
						stack.resize(size);
					}
					else if(up < pos[u]) stack.push_back(id);
					else{
						belongs[g.edge[id].from].push_back((int)comp_vertex.size());
						belongs[g.edge[id].to].push_back((int)comp_vertex.size());
						comp_vertex.push_back({g.edge[id].from, g.edge[id].to});
						comp_edge.push_back({id});
						bridge.push_back(id);
					}
				}
			}
			return low;
		};
		for(auto u: src) if(was[u] != attempt) recurse(recurse, u, -1);
	}
	template<class T>
	void run(const graph<T> &g, const vector<int> &src){
		assert(g.n <= n);
		for(auto u: src) assert(0 <= u && u < g.n);
		comp_vertex.clear();
		comp_edge.clear();
		bridge.clear();
		++ attempt;
		_run(g, src);
	}
	template<class T>
	void run_all(const graph<T> &g){
		assert(g.n <= n);
		comp_vertex.clear();
		comp_edge.clear();
		bridge.clear();
		++ attempt;
		vector<int> src(g.n);
		iota(src.begin(), src.end(), 0);
		_run(g, src);
	}
	// Check if u is visited during the last run-like call.
	bool visited(int u) const{
		assert(0 <= u && u < n);
		return was[u] == attempt;
	}
	bool is_articulation_point(int u) const{
		assert(0 <= u && u < n && visited(n));
		return (int)belongs[u].size() >= 2;
	}
	bool is_bridge_component(int i) const{
		assert(0 <= i && i < (int)comp_vertex.size());
		return (int)comp_edge[i].size() == 1;
	}
	// # of 2-vertex-connected components
	int count() const{
		return (int)comp_vertex.size();
	}
};

int n, visited[300300];
ll ans, dp0[300300], dp[300300];
vector<int> adj[300300];

int dfs1(int s, int pa = -1){
	visited[s] = 1;
	if (s < n) dp[s] = 1;
	
	for (auto &v:adj[s]) if (v!=pa){
		dp[s] += dfs1(v, s) - 1;
	}

	return dp[s];
}

void dfs2(int s, int pa = -1){
	for (auto &v:adj[s]) if (v!=pa) dfs2(v, s);
	if (s < n) return;

	ll rem = n - dp0[s];
	for (auto &v:adj[s]) if (v!=pa){
		ans -= (dp0[s]-1) * dp[v] * (dp[v]-1);
		rem -= dp[v]-1;
	}

	rem++;
	ans -= (dp0[s]-1) * rem * (rem-1);
}

int main(){
	int m;
	scanf("%d %d", &n, &m);

	vector<array<int, 2>> E;

	for (int i=0;i<m;i++){
		int x, y;
		scanf("%d %d", &x, &y);
		--x, --y;
		E.push_back({x, y});
	}

	graph<int> G(n, E);
	biconnected_components BCC(G);

	int sz = n + BCC.count();
	for (int i=0;i<n;i++){
		for (auto &x:BCC.belongs[i]){
			assert(n+x < sz);
			adj[i].push_back(n+x);
			adj[n+x].push_back(i);
		}
	}

	for (int i=0;i<sz;i++){
		if (i<n) dp0[i] = dp[i] = 1;
		else dp0[i] = dp[i] = BCC.comp_vertex[i-n].size();
	}

	for (int i=0;i<sz;i++) if (!visited[i]){
		ll v = dfs1(i);
		if (v <= 2) continue;
		
		ans += v * (v-1) * (v-2);
		dfs2(i);
	}

	printf("%lld\n", ans);
}

Compilation message

count_triplets.cpp: In instantiation of 'biconnected_components::_run<int>::<lambda(auto:23, int, int)> [with auto:23 = biconnected_components::_run<int>::<lambda(auto:23, int, int)>]':
count_triplets.cpp:186:42:   required from 'void biconnected_components::_run(const graph<T>&, const std::vector<int>&) [with T = int]'
count_triplets.cpp:207:7:   required from 'void biconnected_components::run_all(const graph<T>&) [with T = int]'
count_triplets.cpp:118:63:   required from 'biconnected_components::biconnected_components(const graph<T>&) [with T = int]'
count_triplets.cpp:271:30:   required from here
count_triplets.cpp:140:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  140 |     if(g.ignore && g.ignore(id) || id == pe) continue;
      |        ~~~~~~~~~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:259:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  259 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:265:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  265 |   scanf("%d %d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 10844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 10844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 56292 KB Output is correct
2 Correct 99 ms 56116 KB Output is correct
3 Incorrect 118 ms 51940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 11352 KB Output is correct
2 Correct 5 ms 11212 KB Output is correct
3 Correct 3 ms 11100 KB Output is correct
4 Correct 3 ms 11352 KB Output is correct
5 Correct 3 ms 11100 KB Output is correct
6 Correct 3 ms 11100 KB Output is correct
7 Correct 3 ms 11100 KB Output is correct
8 Correct 3 ms 11100 KB Output is correct
9 Correct 4 ms 11100 KB Output is correct
10 Incorrect 3 ms 11100 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 46524 KB Output is correct
2 Correct 136 ms 46276 KB Output is correct
3 Correct 162 ms 46252 KB Output is correct
4 Correct 113 ms 46652 KB Output is correct
5 Correct 146 ms 46260 KB Output is correct
6 Correct 152 ms 59892 KB Output is correct
7 Correct 151 ms 55212 KB Output is correct
8 Correct 134 ms 52788 KB Output is correct
9 Correct 133 ms 50248 KB Output is correct
10 Incorrect 154 ms 46852 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 11096 KB Output is correct
2 Correct 3 ms 11100 KB Output is correct
3 Correct 3 ms 11100 KB Output is correct
4 Correct 4 ms 11096 KB Output is correct
5 Correct 2 ms 11128 KB Output is correct
6 Correct 3 ms 11100 KB Output is correct
7 Correct 3 ms 11100 KB Output is correct
8 Correct 4 ms 10912 KB Output is correct
9 Correct 3 ms 11100 KB Output is correct
10 Correct 3 ms 11100 KB Output is correct
11 Correct 3 ms 11100 KB Output is correct
12 Correct 3 ms 11376 KB Output is correct
13 Correct 4 ms 11100 KB Output is correct
14 Correct 3 ms 11100 KB Output is correct
15 Correct 4 ms 11100 KB Output is correct
16 Incorrect 3 ms 11100 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 46776 KB Output is correct
2 Correct 128 ms 46080 KB Output is correct
3 Correct 154 ms 44696 KB Output is correct
4 Correct 124 ms 41000 KB Output is correct
5 Correct 90 ms 37320 KB Output is correct
6 Correct 86 ms 34496 KB Output is correct
7 Correct 92 ms 33732 KB Output is correct
8 Correct 73 ms 32952 KB Output is correct
9 Correct 70 ms 32736 KB Output is correct
10 Correct 79 ms 32444 KB Output is correct
11 Correct 66 ms 31940 KB Output is correct
12 Correct 66 ms 31936 KB Output is correct
13 Correct 63 ms 32100 KB Output is correct
14 Correct 75 ms 37824 KB Output is correct
15 Correct 165 ms 55216 KB Output is correct
16 Correct 135 ms 51640 KB Output is correct
17 Correct 156 ms 53056 KB Output is correct
18 Correct 125 ms 49072 KB Output is correct
19 Incorrect 104 ms 40784 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 10844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 10844 KB Output isn't correct
2 Halted 0 ms 0 KB -