oj.uz

Submission #146742

# Submission time Handle Problem Language Result Execution time Memory
146742 2019-08-25T19:32:03 Z abacaba Shymbulak (IZhO14_shymbulak) C++14
100 / 100
 317 ms 21884 KB 
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <deque>
using namespace std;

#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<long long, long long>
#define ld long double
#define pll pair<long long, long long>

#define int long long

const int inf = 2e9;
const int N = 2e5 + 15;
int n, mx, parent[N];
pii d[N];
vector <int> g[N], cycle;
bool used[N], is[N];
int sz;
pii ans;
map <int, int> cnt;
multiset <int> cur;

bool find_cycle(int v, int p = -1) {
	used[v] = true;
	parent[v] = p;
	for(int to : g[v]) {
		if(to != p) {
			if(used[to]) {
				int u = v;
				is[u] = true;
				cycle.pb(u);
				++sz;
				while(u != to) {
					++sz;
					u = parent[u];
					cycle.pb(u);
					is[u] = true;
				}
				return true;
			}
			else if(find_cycle(to, v))
				return true;
		}
	}
	return false;
}

inline void combine(pii &a, pii b) {
	if(a.f == b.f)
		a.se += b.se;
	else if(a.f < b.f)
		a = b;
}

void dfs_tree(int v, int p = -1) {
	d[v] = mp(0, 1);
	for(int to : g[v])
		if(to != p && !is[to]) {
			dfs_tree(to, v);
			++d[to].f;
			combine(ans, mp(d[v].first + d[to].first, d[v].second * d[to].second));
			combine(d[v], d[to]);
		}
}

#undef int
int main() {
	#define int long long
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		int u, v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	find_cycle(1);
	sz = cycle.size();
	for(int i : cycle)
		dfs_tree(i);
	memset(used, 0, sizeof(used));
	for(int i = 0; i < sz + sz/2; ++i) {
		int now = cycle[i % sz];
		if(i >= sz/2) {
			combine(ans, mp(d[now].f + i + *cur.rbegin(), 0));
			cur.erase(cur.find(d[cycle[i - sz/2]].f - i + sz/2));
		}
		cur.insert(d[now].f - i);
	}
	for(int i = 0; i < sz + sz/2; ++i) {
		int now = cycle[i % sz];
		if(i >= sz / 2) {
			ans.se += d[now].se * cnt[ans.f - d[now].f - i];
			cnt[d[cycle[i - sz/2]].f - i + sz/2] -= d[cycle[i - sz/2]].se;
		}
		cnt[d[now].f - i] += d[now].se;
	}
	cout << ans.se << endl;
	return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5368 KB Output is correct
2 Correct 7 ms 5364 KB Output is correct
3 Correct 8 ms 5368 KB Output is correct
4 Correct 8 ms 5368 KB Output is correct
5 Correct 12 ms 5624 KB Output is correct
6 Correct 12 ms 5624 KB Output is correct
7 Correct 14 ms 5624 KB Output is correct
8 Correct 13 ms 5624 KB Output is correct
9 Correct 12 ms 5624 KB Output is correct
10 Correct 12 ms 5624 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 12376 KB Output is correct
2 Correct 165 ms 12828 KB Output is correct
3 Correct 172 ms 21884 KB Output is correct
4 Correct 127 ms 12376 KB Output is correct
5 Correct 126 ms 12348 KB Output is correct
6 Correct 317 ms 19368 KB Output is correct
7 Correct 256 ms 15840 KB Output is correct
8 Correct 259 ms 19376 KB Output is correct
9 Correct 266 ms 18940 KB Output is correct
10 Correct 262 ms 21500 KB Output is correct
11 Correct 273 ms 19488 KB Output is correct
12 Correct 281 ms 20196 KB Output is correct