oj.uz

Submission #33686

# Submission time Handle Problem Language Result Execution time Memory
33686 2017-10-31T16:09:30 Z RockyB Shymbulak (IZhO14_shymbulak) C++14
100 / 100
 253 ms 32056 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];

void dfs1(int v, int p = - 1) {
	bool ok = 0;
	map <int, int> cnt;
	for (auto to : g[v]) {
		if (to == p || bad[to]) continue;
		dfs1(to, v);
		if (mxv[to].f + 1 == mx) ans += mxv[to].s;
		else if (cnt.count(mx - mxv[to].f - 1)) ans += cnt[mx - mxv[to].f - 1] * mxv[to].s;
		cnt[mxv[to].f + 1] += mxv[to].s;
	}
	mxv[v].s = 1;
	if (sz(cnt)) {
		auto it = --cnt.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);
		}
	}
	{
		multiset <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) {
				mx = max(mx, dp[cycle[i]] + i + *cur.rbegin());
				int l = i - sz / 2;
				cur.erase(cur.find(dp[cycle[l]] - l));
			}
			cur.insert(dp[cycle[i]] - i);
		}
	}
	for (int i = 0; i < sz(cycle) - sz / 2; i++) {
		dfs1(cycle[i]);
	}
	{
		map <int, int> cur;
		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;
		}
	}
	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:80:7: warning: unused variable 'ok' [-Wunused-variable]
  bool ok = 0;
       ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 22692 KB Output is correct
2 Correct 6 ms 22692 KB Output is correct
3 Correct 3 ms 22692 KB Output is correct
4 Correct 0 ms 22692 KB Output is correct
5 Correct 6 ms 22692 KB Output is correct
6 Correct 6 ms 22692 KB Output is correct
7 Correct 0 ms 22692 KB Output is correct
8 Correct 6 ms 22692 KB Output is correct
9 Correct 3 ms 22692 KB Output is correct
10 Correct 0 ms 22692 KB Output is correct
11 Correct 6 ms 22692 KB Output is correct
12 Correct 6 ms 22692 KB Output is correct
13 Correct 6 ms 22692 KB Output is correct
14 Correct 0 ms 22692 KB Output is correct
15 Correct 3 ms 22692 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 22692 KB Output is correct
2 Correct 3 ms 22692 KB Output is correct
3 Correct 0 ms 22692 KB Output is correct
4 Correct 9 ms 22692 KB Output is correct
5 Correct 9 ms 22824 KB Output is correct
6 Correct 9 ms 22976 KB Output is correct
7 Correct 3 ms 22824 KB Output is correct
8 Correct 13 ms 22824 KB Output is correct
9 Correct 6 ms 22824 KB Output is correct
10 Correct 6 ms 22824 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 25596 KB Output is correct
2 Correct 106 ms 25992 KB Output is correct
3 Correct 76 ms 31740 KB Output is correct
4 Correct 66 ms 25860 KB Output is correct
5 Correct 63 ms 25860 KB Output is correct
6 Correct 253 ms 28236 KB Output is correct
7 Correct 173 ms 27312 KB Output is correct
8 Correct 136 ms 29028 KB Output is correct
9 Correct 133 ms 29160 KB Output is correct
10 Correct 109 ms 29756 KB Output is correct
11 Correct 123 ms 31744 KB Output is correct
12 Correct 129 ms 32056 KB Output is correct