oj.uz

답안 #33682

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
33682 2017-10-31T15:27:52 Z RockyB 관광지 (IZhO14_shymbulak) C++14
50 / 100
 1500 ms 52676 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)5e5 + 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 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];
map <int, int> cnt[N];

void dfs1(int v, int p = - 1) {
	bool ok = 0;
	for (auto to : g[v]) {
		if (to == p || bad[to]) continue;
		dfs1(to, v);
	}
	for (auto to : g[v]) {
		if (to == p || bad[to]) continue;
		if (mxv[to].f + 1 == mx) ans += mxv[to].s;
		else if (cnt[v].count(mx - mxv[to].f - 1)) ans += cnt[v][mx - mxv[to].f - 1] * mxv[to].s;
		cnt[v][mxv[to].f + 1] += mxv[to].s;
	}
	mxv[v].s = 1;
	if (sz(cnt[v])) {
		auto it = --cnt[v].end();
		mxv[v] = *it;
	}
	else mxv[v] = {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]);
	}
	{
		map <int, int> cur;
		for (int i = 0; i < sz / 2; i++) {
			cycle.pb(cycle[i]);
		}
		for (int i = 0; i < sz + sz / 2; i++) {
			if (i >= sz / 2) {
				if (cur.count(mx - dp[cycle[i]] - i)) ans += (ll)mxv[cycle[i]].s * cur[mx - dp[cycle[i]] - i];
				int l = i - sz / 2;
				cur[dp[cycle[l]] - l] -= mxv[cycle[l]].s;
			}
			cur[dp[cycle[i]] - i] += mxv[cycle[i]].s;
		}
		cerr << nl;
	}
	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")
 ^
shymbulak.cpp: In function 'void dfs1(int, int)':
shymbulak.cpp:81:7: warning: unused variable 'ok' [-Wunused-variable]
  bool ok = 0;
       ^

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 46128 KB Output is correct
2 Correct 19 ms 46128 KB Output is correct
3 Correct 16 ms 46128 KB Output is correct
4 Correct 13 ms 46128 KB Output is correct
5 Correct 9 ms 46392 KB Output is correct
6 Correct 9 ms 46412 KB Output is correct
7 Correct 19 ms 46392 KB Output is correct
8 Correct 16 ms 46392 KB Output is correct
9 Correct 6 ms 46392 KB Output is correct
10 Correct 16 ms 46392 KB Output is correct

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 51276 KB Output is correct
2 Correct 86 ms 50748 KB Output is correct
3 Execution timed out 1500 ms 52676 KB Execution timed out
4 Halted 0 ms 0 KB -