oj.uz

답안 #33670

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
33670 2017-10-31T14:01:31 Z RockyB 관광지 (IZhO14_shymbulak) C++14
20 / 100
 1500 ms 16940 KB 
/// In The Name Of God
 
#pragma GCC optimize("Ofast")
#pragma GCC target_("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")
 
#include <bits/stdc++.h>
 
#define f first
#define s second
 
#define pb push_back
#define pp pop_back
#define mp make_pair
 
#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()
 
#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
#define nl '\n'
#define ioi exit(0);
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
 
const int N = (int)2e5 + 7, inf = (int)1e9 + 7, mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
 
using namespace std;
 
int get__int() {
	char x = getchar();
	int res = 0;
	while (!isdigit(x)) res = res * 10 + x - '0', x = getchar();
	while (isdigit(x)) res = res * 10 + x - '0', x = getchar();
	return res;
}
 
int n;
vector <int> g[N];

vector <int> cycle;
int from[N];
bool was[N], bad[N];
void find_cycle(int v = 1, int p = -1) {
	was[v] = 1;
	from[v] = p;
	for (auto to : g[v]) {
		if (to == p) continue;
		if (was[to] && !sz(cycle)) {
			int x = v;
			while (1) {
				cycle.pb(x);
				bad[x] = 1;
				if (x == to) break;
				x = from[x];
			}
		}
		else if (!was[to]) find_cycle(to, v);
	}
}

ll ans;
int mx;
int dp[N];
void dfs(int v, int p = -1) {
	priority_queue <int> st;
	for (auto to : g[v]) {
		if (to == p || bad[to]) continue;
		dfs(to, v);
		st.push(dp[to] + 1);
		dp[v] = max(dp[v], dp[to] + 1);
	}
	int cur = 0;
	for (int i = 1, j = sz(st); i <= min(2, j); i++) {
		cur += st.top();
		st.pop();
	}
	mx = max(mx, cur);
}
pair <int, int> mxv[N];
pair <int, int> dfs1(int v, int p = - 1) {
	map <int, int> cnt, cnt1;
	for (auto to : g[v]) {
		if (to == p || bad[to]) continue;
		pair <int, int> res = dfs1(to, v);
		cnt[res.f + 1] += res.s;
		cnt1[dp[to] + 1]++;
	}
	mxv[v].s = 1;
	if (sz(cnt)) {
		auto it = --cnt1.end();
		if (it -> s >= 2) {
			if (2 * it -> f == mx) {
				ans += (ll)it -> s * (it -> s - 1) / 2;
			}
		}
		else if (sz(cnt) > 1) {
			auto it = --cnt.end();
			pair <int, int> l1 = *it;
			--it;
			pair <int, int> l2 = *it;
			if (l1.f + l2.f == mx) {
				ans += (ll)l1.s * l2.s;
			}
		}
		else if (it -> f == mx) ans++;
		return mxv[v] = *--cnt.end();
	}
	else return {0, 1};
}
int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
		freopen ("C.out", "w", stdout);
	#endif
	Kazakhstan
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int v, u;
		cin >> v >> u;
		g[v].pb(u);
		g[u].pb(v);
	}
	find_cycle();
	int sz = sz(cycle);
	for (auto it : cycle) {
		bool ok = 0;
		for (auto to : g[it]) {
			if (!bad[to]) {
				ok = 1;
				break;
			}
		}
		if (ok) {
			dfs(it);
			mx = max(mx, dp[it] + sz / 2);
		}
	}
	for (int i = 0; i < sz; i++) {
		for (int j = i + 1; j < sz; j++) {
			mx = max(mx, dp[cycle[i]] + dp[cycle[j]] + min(i + (sz - j), j - i));
		}
	}
	for (int i = 0; i < sz(cycle); i++) {
		dfs1(cycle[i]);
	}
	{
		//cerr << mx << ' ' << ans << nl;
	}
	/*
	{
//		for (auto it : )
	}
	
	map <int, int> cnt;
	for (int i = 0; i < sz(cycle); i++) {
		if (i >= 0) {
			ans = 0;
			ans += (ll)mxv[cycle[i]].s * cnt[mx - dp[cycle[i]] - i];
			cerr << cycle[i] << ' ' << ans << nl;
		}
		if (i >= extra) {
			int l = i - extra;
			//cnt[dp[cycle[l] - l]] -= mxv[cycle[l]].s;
		}
		cnt[dp[cycle[i]] - i] += mxv[cycle[i]].s; 
	}
	cerr << ans;
	cout << ans;*/
	for (int i = 0; i < sz; i++) {
		for (int j = i + 1; j < sz; j++) {
			int x = dp[cycle[i]] + dp[cycle[j]] + min(i + (sz - j), j - i);
			if (x == mx) {
				int x = mxv[cycle[i]].s * 1ll * mxv[cycle[j]].s;
				ans += x;
				if (i + (sz - j) == (j - i)) ans += x;
			}
		}
	}
	//cerr << ans;
	cout << ans;
	ioi
}

Compilation message

shymbulak.cpp:4:0: warning: ignoring #pragma GCC target_ [-Wunknown-pragmas]
 #pragma GCC target_("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")
 ^

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 10388 KB Output is correct
2 Correct 0 ms 10388 KB Output is correct
3 Correct 3 ms 10388 KB Output is correct
4 Correct 0 ms 10388 KB Output is correct
5 Incorrect 0 ms 10388 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

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

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 13292 KB Output is correct
2 Correct 89 ms 13688 KB Output is correct
3 Execution timed out 1500 ms 16940 KB Execution timed out
4 Halted 0 ms 0 KB -