제출 #379595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
379595		SavicS	관광지 (IZhO14_shymbulak)	C++14	0 / 100	75 ms	11372 KiB

shymbulak

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 200005;
const int inf = 1e9 + 5;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n;

vector<int> g[maxn];

vector<int> krug;

int par[maxn];
int visited[maxn];
void dfs1(int v, int p){
	par[v] = p;
	visited[v] = 1;
	for(auto u : g[v]){
		if(u == p)continue;
		if(!visited[u])dfs1(u, v);
		else{
			if(visited[u] == 1){
				int a = v;
				while(a != u){
					krug.pb(a);
					a = par[a];
				}
				krug.pb(u);
			}
		}
	}
	visited[v] = 2;
}

pii kol[maxn];
bool bio[maxn];

int mx = 0;
int br = 0;
bool was[maxn];
int dia = 0;
int brdia = 0;
int dfs2(int v, int duz){
	if(duz == mx)br += 1;
	if(duz > mx){
		mx = duz;
		br = 1;
	}
	was[v] = 1;
	int best = duz;
	for(auto u : g[v]){
		if(!was[u]){
			int dist = dfs2(u, duz + 1);
//			dia = max(dia, best + dist - 2 * duz);
			if(best + dist - 2 * duz == dia)brdia += 1;
			if(best + dist - 2 * duz > dia){
				dia = best + dist - 2 * duz;
				brdia = 1;
			}
			best = max(best, dist);
		}
	}
	return best;
}

multiset<int> ms1;
void ins1(pii x){
	int a = x.fi;
	int b = x.se;
	while(b--)ms1.insert(a);	
}
void del1(pii x){
	int a = x.fi;
	int b = x.se;
	while(b--)ms1.erase(ms1.find(a));		
}

multiset<int> ms2;
void ins2(pii x){
	int a = x.fi;
	int b = x.se;
	while(b--)ms2.insert(a);
}
void del2(pii x){
	int a = x.fi;
	int b = x.se;
	while(b--)ms2.erase(ms2.find(a));		
}

int main()
{
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
	cin >> n;
	ff(i,1,n){
		int u, v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	dfs1(1, -1);
	for(auto c : krug)was[c] = 1;
	ff(i,0,sz(krug) - 1){
		mx = 0;
		br = 0;
		dfs2(krug[i], 0);
		kol[i] = {mx, br};
	}
	int len = sz(krug);
	// max najmanju dist izmedju dva cvora
	int dist = len / 2;
	ins1(kol[0]);
	int ans = 0;
	int ima = 0;
	// i - j <= len / 2
	ff(i,1,dist - 1){
		int a = kol[i].fi + i + *ms1.rbegin();
		if(a == ans)ima += kol[i].se * ms1.count(*ms1.rbegin());
		if(a > ans){
			ans = a;
			ima = kol[i].se * ms1.count(*ms1.rbegin());
		}
//		ms1.insert(kol[i].fi - i);	
		ins1({kol[i].fi - i, kol[i].se});
	}
	ff(i,dist,len - 1){
//		ans = max(ans, kol[i].fi + i + *ms1.rbegin());
//		cout << "i: " << i << endl;
		int a = kol[i].fi + i + *ms1.rbegin();
//		cout << "a: " << a << endl;
		int x = *ms1.rbegin();
		if(a == ans){
			if(len % 2 == 0 && x == kol[i - dist].fi - (i - dist))ima += 2 * kol[i].se * ms1.count(x);
			else ima += kol[i].se * ms1.count(x);
		}
		if(a > ans){
			ans = a;
			if(len % 2 == 0 && x == kol[i - dist].fi - (i - dist))ima = 2 * kol[i].se * ms1.count(x);
			else ima = kol[i].se * ms1.count(x);
		}
		if(!ms2.empty()){
//			ans = max(ans, kol[i].fi - i + *ms2.rbegin() + len);
			int b = kol[i].fi - i + *ms2.rbegin() + len;
//			cout << "b: " << b << endl;
			if(b == ans)ima += kol[i].se * ms2.count(*ms2.rbegin());
			if(b > ans){
				ans = b;
				ima = kol[i].se * ms2.count(*ms2.rbegin());
			}	
		}
//		cout << "------------------------" << endl;
//		cout << endl;
		
//		ms1.erase(ms1.find(kol[i - dist].fi - (i - dist)));
		
		del1({kol[i - dist].fi - (i - dist), kol[i - dist].se});
			
//		ms1.insert(kol[i].fi - i);
//		ms2.insert(kol[i - dist].fi + (i - dist));
		
		ins1({kol[i].fi - i, kol[i].se});
		ins2({kol[i - dist].fi + (i - dist), kol[i - dist].se});
	}
	// i - j > len / 2
	if(dia == ans)ima += brdia;
	if(dia > ans)ima = brdia;
	cout << ima << endl;
	return 0;
}
/**

6
1 2
1 3
2 4
4 3
4 5
4 6

8
1 2
1 3
1 7
7 8
2 4
4 3
4 5
4 6

// probati bojenje sahovski ili slicno

**/

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