제출 #379518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
379518		SavicS	관광지 (IZhO14_shymbulak)	C++14	0 / 100	83 ms	11344 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];
void dfs2(int v, int duz){
	if(duz > mx){
		mx = duz;
		br = 0;
	}
	if(mx == duz)br += 1;
	was[v] = 1;
	for(auto u : g[v]){
		if(!was[u])dfs2(u, duz + 1);
	}
}

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[krug[i]] = {mx, br};
	}
	int len = sz(krug);
	int mxdist = len / 2;
	int j = 0;
	while(j < len)krug.pb(krug[j++]);
	multiset<int> ms;
	ff(i,0,mxdist - 1){
		int x = kol[krug[i]].se;
		while(x--)ms.insert(i - kol[krug[i]].fi);
	}
	int najv = 0;
	int ima = 0;
	ff(i,mxdist,sz(krug) - 1){
		if(bio[krug[i]])break;
		bio[krug[i]] = 1;
		if(kol[krug[i]].fi + i - *ms.begin() > najv){
			najv = kol[krug[i]].fi + i - *ms.begin();
			ima = 0;
		}
		if(kol[krug[i]].fi + i - *ms.begin() == najv)ima += kol[krug[i]].se * ms.count(*ms.begin());
		{
			int x = kol[krug[i - mxdist]].se;
			while(x--)ms.erase(ms.find(i - mxdist - kol[krug[i - mxdist]].fi));
		}
		{
			int x = kol[krug[i]].se;
			while(x--)ms.insert(i - kol[krug[i]].fi);
		}
	}
	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