제출 #975975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
975975		qwerasdfzxcl	철인 이종 경기 (APIO18_duathlon)	C++17	100 / 100	185 ms	58356 KiB

count_triplets

#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 nn, int s, int pa = -1){
	for (auto &v:adj[s]) if (v!=pa) dfs2(nn, v, s);
	if (s < n) return;

	ll rem = nn - 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(v, i);
	}

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

컴파일 시 표준 에러 (stderr) 메시지

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: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 15 / 15
• Subtask 7: 20 / 20
• Subtask 8: 8 / 8
• Subtask 9: 10 / 10