#include <cstdio>
#include <cstring>
#include <vector>
const int N = 200000;
std::vector<int> g[N], c;
int n;
bool u[N], cyc[N];
int go(int v, int pr = -1)
{
u[v] = 1;
for (int i = 0; i < (int)g[v].size(); ++i) if (g[v][i] != pr) {
if (u[g[v][i]]) {
cyc[v] = 1;
cyc[g[v][i]] = 1;
c.push_back(g[v][i]);
c.push_back(v);
return 1;
}
int k;
if (k = go(g[v][i], v)) {
if (k == -1 || c.front() == v) return -1;
cyc[v] = 1;
c.push_back(v);
return 1;
}
}
return 0;
}
struct item {
int max;
long long amt;
item(int max_ = (1 << 31) >> 2, long long amt_ = 0) {
max = max_;
amt = amt_;
}
item operator+(item arg) {
item res;
res.max = std::max(max, arg.max);
if (res.max == max) res.amt += amt;
if (res.max == arg.max) res.amt += arg.amt;
return res;
}
} t[N << 2];
item fres;
int last;
void far(int v, int cur = 0, int pr = -1)
{
fres = fres + item(cur, 1);
if (fres.max == cur) last = v;
for (int i = 0; i < (int)g[v].size(); ++i) if (g[v][i] != pr && !cyc[g[v][i]]) far(g[v][i], cur + 1, v);
}
std::vector<int> path;
bool find(int v, int d, int pr = -1)
{
if (!d) {
path.push_back(v);
return 1;
}
for (int i = 0; i < (int)g[v].size(); ++i) if (!cyc[g[v][i]] && g[v][i] != pr && find(g[v][i], d - 1, v)) {
path.push_back(v);
return 1;
}
return 0;
}
item get(int l, int r)
{
item res;
for (l += c.size() << 1, r += c.size() << 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = res + t[l++];
if (r & 1) res = res + t[--r];
}
return res;
}
int cnt = 0;
int gogog(int v, int t)
{
u[v] = 1;
if (v == t) {
cnt += cyc[v];
return 0;
}
int k;
for (int i = 0; i < (int)g[v].size(); ++i) if (!u[g[v][i]] && (k = gogog(g[v][i], t)) != -1) {
cnt += cyc[v];
return k + 1;
}
return -1;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
int a, b;
scanf("%d%d", &a, &b);
g[a - 1].push_back(b - 1);
g[b - 1].push_back(a - 1);
}
go(0);
item ans;
for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) {
cnt = 0;
memset(u, 0, n);
item cur(gogog(i, j), 1);
if (cnt - 1 > (int)c.size() / 2) cur.max = cur.max - 2 * (cnt - 1) + (int)c.size();
cur.amt += c.size() & 1 ^ 1 && (cnt == c.size() / 2 + 1);
ans = ans + cur;
}
printf("%lld\n", ans.amt);
return 0;
for (int i = 0; i < (int)c.size(); ++i) {
cyc[c[i]] = 0;
fres = item();
far(c[i]);
fres.max -= i;
t[c.size() * 2 + i] = fres;
fres.max -= c.size();
t[c.size() * 3 + i] = fres;
int from = last;
fres = item();
far(last);
path.clear();
find(from, fres.max);
item cur;
cur.max = path.size() - 1;
if (path.size() & 1) {
int c = path[(int)path.size() >> 1];
cyc[c] = 1;
int amt = 0;
for (int i = 0; i < (int)g[c].size(); ++i) if (!cyc[g[c][i]]) {
fres = item();
far(g[c][i]);
if (fres.max + 1 == path.size() / 2) {
cur.amt += fres.amt * amt;
amt += fres.amt;
}
}
cyc[c] = 0;
} else {
int u = path[path.size() >> 1], v = path[path.size() - 1 >> 1];
fres = item();
far(u, 0, v);
int amt = fres.amt;
fres = item();
far(v, 0, u);
cur.amt = fres.amt * amt;
}
ans = ans + cur;
printf("cur %d %lld\n", cur.max, cur.amt);
cyc[c[i]] = 1;
}
for (int i = (int)c.size() * 2 - 1; i; --i) t[i] = t[i << 1 | 1] + t[i << 1];
for (int i = 0; i < (int)c.size(); ++i) {
item cur = get((c.size() + 1 >> 1) + i, c.size() + i);
cur.max += c.size() + i + t[c.size() * 2 + i].max + i;
cur.amt *= t[2 * c.size() + i].amt;
ans = ans + cur;
}
printf("%lld\n", ans.amt);
return 0;
}
Compilation message
shymbulak.cpp: In function 'int go(int, int)':
shymbulak.cpp:22:9: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
22 | if (k = go(g[v][i], v)) {
| ~~^~~~~~~~~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:113:23: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
113 | cur.amt += c.size() & 1 ^ 1 && (cnt == c.size() / 2 + 1);
| ~~~~~~~~~^~~
shymbulak.cpp:113:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | cur.amt += c.size() & 1 ^ 1 && (cnt == c.size() / 2 + 1);
| ~~~~^~~~~~~~~~~~~~~~~~~
shymbulak.cpp:140:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | if (fres.max + 1 == path.size() / 2) {
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
shymbulak.cpp:147:57: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
147 | int u = path[path.size() >> 1], v = path[path.size() - 1 >> 1];
| ~~~~~~~~~~~~^~~
shymbulak.cpp:161:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
161 | item cur = get((c.size() + 1 >> 1) + i, c.size() + i);
| ~~~~~~~~~^~~
shymbulak.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
shymbulak.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
102 | scanf("%d%d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
17484 KB |
Output is correct |
| 2 |
Correct |
8 ms |
17484 KB |
Output is correct |
| 3 |
Correct |
11 ms |
17432 KB |
Output is correct |
| 4 |
Correct |
11 ms |
17484 KB |
Output is correct |
| 5 |
Correct |
9 ms |
17484 KB |
Output is correct |
| 6 |
Correct |
9 ms |
17412 KB |
Output is correct |
| 7 |
Correct |
11 ms |
17412 KB |
Output is correct |
| 8 |
Correct |
8 ms |
17508 KB |
Output is correct |
| 9 |
Correct |
9 ms |
17508 KB |
Output is correct |
| 10 |
Correct |
8 ms |
17484 KB |
Output is correct |
| 11 |
Correct |
10 ms |
17464 KB |
Output is correct |
| 12 |
Correct |
10 ms |
17508 KB |
Output is correct |
| 13 |
Correct |
17 ms |
17508 KB |
Output is correct |
| 14 |
Correct |
277 ms |
17512 KB |
Output is correct |
| 15 |
Correct |
334 ms |
17512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1227 ms |
17560 KB |
Output is correct |
| 2 |
Correct |
928 ms |
17484 KB |
Output is correct |
| 3 |
Execution timed out |
1587 ms |
17484 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1550 ms |
20604 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
