제출 #563717

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
563717		racsosabe	관광지 (IZhO14_shymbulak)	C++14	100 / 100	162 ms	20924 KiB

shymbulak

#include<bits/stdc++.h>
using namespace::std;

const int N = 200000 + 5;

struct MaxStack{
	stack<pair<pair<int, int>, pair<int, int>>> S;
	MaxStack(){}
	
	void emplace(pair<int, int> x){
		pair<int, int> maximum = x;
		if(S.empty()) S.emplace(make_pair(x, maximum));
		else{
			if(maximum.first == S.top().second.first){
				maximum.second += S.top().second.second;
			}
			else if(maximum.first < S.top().second.first){
				maximum = S.top().second;
			}
			S.emplace(make_pair(x, maximum));
		}
	}

	bool empty(){
		return S.empty();
	}

	pair<int, int> top(){
		return S.top().first;
	}

	pair<int, int> get_max(){
		return S.empty() ? make_pair(-1000000000, 0) : S.top().second;
	}

	void pop(){
		S.pop();
	}
};

struct MaxQueue{
	MaxStack in, out;

	void emplace(pair<int, int> x){
		in.emplace(x);
	}

	void pop(){
		if(out.empty()){
			while(!in.empty()){
				pair<int, int> x = in.top(); in.pop();
				out.emplace(x);
			}
		}
		out.pop();
	}

	pair<int, int> get_max(){
		pair<int, int> max_in = in.get_max();
		pair<int, int> max_out = out.get_max();
		if(max_in.first < max_out.first) max_in = max_out;
		else if(max_in.first == max_out.first) max_in.second += max_out.second;
		return max_in;
	}
};

int n;
int h[N];
int cnt[N];
int deg[N];
int best_h[N];
bool cycle[N];
int furthest[N];
vector<int> G[N];
long long memo[N];
vector<int> nodes_in_cycle;

void mark_cycle(){
	queue<int> Q;
	for(int i = 1; i <= n; i++) cycle[i] = true;
	for(int i = 1; i <= n; i++){
		if(deg[i] == 1){
			Q.emplace(i);
			cycle[i] = false;
			deg[i] = 0;
		}
	}
	while(!Q.empty()){
		int u = Q.front(); Q.pop();
		for(int v : G[u]){
			deg[v]--;
			if(deg[v] == 1){
				Q.emplace(v);
				cycle[v] = false;
			}
		}
	}
}

void compute(int u, int p = -1){
	h[u] = best_h[u] = 0;
	cnt[u] = 1;
	furthest[u] = 0;
	memo[u] = 1;
	int maxi_best_h = 0;
	int cnt_best_h = 0;
	for(int v : G[u]){
		if(v == p or cycle[v]) continue;
		h[v] = h[u] + 1;
		compute(v, u);
		int cur_best = best_h[v] + 1 + maxi_best_h;
		if(furthest[u] < cur_best){
			furthest[u] = cur_best;
			memo[u] = 2ll * cnt_best_h * cnt[v];
		}
		else if(furthest[u] == cur_best){
			memo[u] += 2ll * cnt_best_h * cnt[v];
		}
		if(maxi_best_h == best_h[v] + 1) cnt_best_h += cnt[v];
		else if(maxi_best_h < best_h[v] + 1){
			maxi_best_h = best_h[v] + 1;
			cnt_best_h = cnt[v];
		}
		if(best_h[v] + 1 == best_h[u]){
			cnt[u] += cnt[v];
		}
		else if(best_h[v] + 1 > best_h[u]){
			best_h[u] = best_h[v] + 1;
			cnt[u] = cnt[v];
		}
	}
}

void get_nodes_in_cycle(){
	for(int i = 1; i <= n; i++){
		if(cycle[i]){
			stack<int> Q;
			Q.emplace(i);
			cycle[i] = false;
			while(!Q.empty()){
				int u = Q.top(); Q.pop();
				nodes_in_cycle.emplace_back(u);
				for(int v : G[u]){
					if(cycle[v]){
						Q.emplace(v);
						cycle[v] = false;
					}
				}
			}
			break;
		}
	}
}

void compute_ranges(int k){
	MaxQueue r;
	for(int i = 0; i <= k; i++){
		int x = nodes_in_cycle[i];
		r.emplace(make_pair(best_h[x] + i, cnt[x]));
	}
	for(int i = 0; i < nodes_in_cycle.size(); i++){
		int x = nodes_in_cycle[i];
		r.pop();
		pair<int, int> right_best = r.get_max();
		right_best.first -= i - best_h[x];
		if(furthest[x] == right_best.first) memo[x] += 1ll * right_best.second * cnt[x];
		else if(furthest[x] < right_best.first){
			furthest[x] = right_best.first;
			memo[x] = 1ll * right_best.second * cnt[x];
		}
		int j = i + k + 1;
		int y = nodes_in_cycle[j % nodes_in_cycle.size()];
		r.emplace(make_pair(best_h[y] + j, cnt[y]));
	}
}

long long get_best(){
	int L = nodes_in_cycle.size() / 2;
	compute_ranges(L);
	reverse(nodes_in_cycle.begin(), nodes_in_cycle.end());
	compute_ranges(L);
	int best_len = 0;
	long long ans = 0;
	for(int i = 1; i <= n; i++){
		if(furthest[i] == best_len) ans += 1ll * memo[i];
		else if(furthest[i] > best_len){
			ans = 1ll * memo[i];
			best_len = furthest[i];
		}
	}
	return ans;
}


long long solve(){
	mark_cycle();
	for(int i = 1; i <= n; i++) if(cycle[i]) compute(i);
	get_nodes_in_cycle();
	return get_best() >> 1;
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		int u, v;
		scanf("%d %d", &u, &v);
		G[u].emplace_back(v);
		G[v].emplace_back(u);
		deg[u]++; deg[v]++;
	}
	printf("%lld\n", solve());
	return 0;
}

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

shymbulak.cpp: In function 'void compute_ranges(int)':
shymbulak.cpp:161:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |  for(int i = 0; i < nodes_in_cycle.size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:203:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  203 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
shymbulak.cpp:206:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  206 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 50 / 50