oj.uz

답안 #563717

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
563717 2022-05-18T03:45:20 Z racsosabe 관광지 (IZhO14_shymbulak) C++14
100 / 100
 162 ms 20924 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;
	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;
}

Compilation message

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.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 4 ms 5204 KB Output is correct
6 Correct 4 ms 5332 KB Output is correct
7 Correct 5 ms 5332 KB Output is correct
8 Correct 4 ms 5332 KB Output is correct
9 Correct 5 ms 5332 KB Output is correct
10 Correct 5 ms 5332 KB Output is correct

Subtask #3
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 10788 KB Output is correct
2 Correct 73 ms 12600 KB Output is correct
3 Correct 43 ms 12724 KB Output is correct
4 Correct 42 ms 12352 KB Output is correct
5 Correct 42 ms 12368 KB Output is correct
6 Correct 162 ms 18376 KB Output is correct
7 Correct 88 ms 15820 KB Output is correct
8 Correct 90 ms 19708 KB Output is correct
9 Correct 92 ms 19808 KB Output is correct
10 Correct 77 ms 20412 KB Output is correct
11 Correct 101 ms 20140 KB Output is correct
12 Correct 102 ms 20924 KB Output is correct