Submission #563707

# Submission time Handle Problem Language Result Execution time Memory
563707 2022-05-18T03:26:45 Z racsosabe Shymbulak (IZhO14_shymbulak) C++14
0 / 100
65 ms 9728 KB
#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;
	for(int v : G[u]){
		if(v == p or cycle[v]) continue;
		h[v] = h[u] + 1;
		compute(v, u);
		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] += right_best.second;
		else if(furthest[x] < right_best.first){
			furthest[x] = right_best.first;
			memo[x] = right_best.second;
		}
		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] * cnt[i];
		else if(furthest[i] > best_len){
			ans = 1ll * memo[i] * cnt[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;
}

Compilation message

shymbulak.cpp: In function 'void compute_ranges(int)':
shymbulak.cpp:144:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |  for(int i = 0; i < nodes_in_cycle.size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:186:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
shymbulak.cpp:189:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  189 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Incorrect 3 ms 5076 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 9728 KB Output isn't correct
2 Halted 0 ms 0 KB -