/// 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;
^
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
