#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <deque>
using ll = long long;
using namespace std;
const int N = 2000 * 100 + 7;
typedef vector<ll> vi;
typedef vector<vi> vp;
typedef vector<bool> vb;
#define ad push_back
#define mp make_pair
int n;
struct vt {
ll vl, how;
int vertex;
vt() {}
vt(ll x,ll e=1,int _v=0) {
vl = x; how = e; vertex = _v;
}
void operator +=(const vt &A){
if (A.vl == vl)how += A.how;
else if (A.vl > vl)*this = A;
}
vt operator+(const ll &c)const {
return vt(vl + c, how,vertex);
}
}ans;
typedef vector<vt> vat;
bool only[N];
vi cur,ham;
int timer = 0;
int up[N];
struct graph {
int len;
vp g;
vi loop;
vb used;
vi par;
vt dp;
vi road;
vat mas;
bool find_loop;
void write() {
cout << len <<'\t'<<"Number of edges"<< endl;
for (int i = 1; i <= len; ++i) {
for (int to : g[i]) {
cout <<"form " <<i << " to " << to << endl;
}
}
cout << "LOOOP" << endl;
for (int to : loop) {
cout << to << " ";
}
cout << endl;
}
void resize(int n) {
find_loop = false;
len = n;
g.ad(vi());
used.resize(n + 2);
par.resize(n + 2);
for (int i = 1; i <= len; ++i) {
g.ad(vi());
used[i] = false;
par[i] = 0;
}
}
void clear() {
for (int i = 0; i <= len; ++i)used[i] = false;
}
void read() {
scanf("%d", &len);
resize(len);
for (int i = 1; i <= len; ++i) {
int u, v;
scanf("%d%d", &u, &v);
g[v].ad(u);
g[u].ad(v);
}
}
ll dfs_size(int v, int p = -1) {
ll w = 1;
if (p == -1) {
cur.ad(v); ham.ad(++timer);
up[v] = timer;
}
for (int to : g[v]) {
if (to == p || only[to])continue;
cur.ad(to); ham.ad(++timer);
up[to] = timer;
w += dfs_size(to, v);
}
return w;
}
void dfs_for_loop(int v,int p=-1) {
if (find_loop)return;
used[v] = true;
par[v] = p;
for (int to : g[v]) {
if (to == p)continue;
if (find_loop)continue;
if (used[to]) {
int e = v;
while (true) {
loop.ad(e);
if (e == to)break;
e = par[e];
}
find_loop = true;
}
else {
dfs_for_loop(to, v);
}
}
}
void cycle() {
clear();
dfs_for_loop(1, 1);
}
void build_MAIN() {
cycle();
for (int to :loop)only[to] = true;
}
vt dfs_find(int v, int p = -1) {
vt d=vt(0,1,v);
for (int to : g[v]) {
if (to == p)continue;
if (used[to])continue;
d +=dfs_find(to, v)+1;
}
return d;
}
void dfs_find_road(int v, int k, int p) {
if (find_loop)return;
par[v] = p;
for (int to : g[v]) {
if (find_loop)break;
if (to == p)continue;
if (to == k) {
int e = to;
par[to] = v;
while (true) {
road.ad(e);
if (e == par[e])break;
e = par[e];
}
find_loop = true;
break;
}
dfs_find_road(to, k, v);
}
}
void solve() {
for (int i = 0; i <= len; ++i)if (used.size() == i)used.ad(0); else used[i] = 0;
vt a = dfs_find(1);
int g1 = a.vertex;
dp = a;
a = dfs_find(g1);
int g2 = a.vertex;
find_loop = 0;
dfs_find_road(g1, g2,g1);
for (int to : road)used[to] = true;
mas.resize(len + 1);
for (int i = 0; i < road.size(); ++i) {
mas[i] = vt();
}
for (int i = 0; i < road.size(); ++i) {
mas[i] = dfs_find(road[i]);
}
int sz = road.size();
vt res = vt(sz - 1, 1, 0);
for (int i = 1; i < sz - 1; ++i) {
ll qan = 2;
if (mas[i].vl == i&&i == sz - i - 1) {
for (int to : g[road[i]]) {
used[to] = true;
used[road[i]] = true;
vt r = dfs_find(to);
if (r.vl == i - 1) {
res.how += qan*r.how;
qan++;
}
}
}
else {
if (mas[i].vl == i) {
res.how += mas[i].how;
}
if (mas[i].vl == sz - i - 1) {
res.how += mas[i].how;
}
}
}
ans += res;
}
}gr[N],root;
void dfs_creat(int s, int v, int p = -1) {
for (int to : root.g[v]) {
if (to == p || only[to])continue;
gr[s].g[up[v]].ad(up[to]);
gr[s].g[up[to]].ad(up[v]);
dfs_creat(s, to, v);
}
}
deque<vt> q;
void add(ll x, ll hw) {
while (q.size() > 0 && q.back().vl <= x) {
hw += q.back().how; q.pop_back();
}
q.push_back(vt(x, hw));
}
void remove(ll hw) {
q.front().how -= hw;
if (q.front().how == 0)q.pop_front();
}
int main() {
//freopen("Text1.txt", "r", stdin);
memset(only, 0, sizeof(only));
root.read();
root.build_MAIN();
int sz = 0;
for (int i = 0; i < root.loop.size(); ++i) {
for (int to : cur)up[to] = 0;
cur.clear(); ham.clear(); timer = 0;
int e = root.dfs_size(root.loop[i]);
gr[sz].resize(e);
dfs_creat(sz, root.loop[i]);
sz++;
}
for (int i = 0; i < sz; ++i) {
gr[i].solve();
}
ll f = 0;
int siz = root.loop.size();
if (siz% 2 == 0) {
add(gr[0].dp.vl, gr[0].dp.how);
f++;
int k = siz / 2;
int qr = 1;
for (int i = 1; i < siz+k; ++i) {
if (qr > k)remove(gr[(i - k - 1+siz)%siz].dp.how);
qr++;
ans += vt(q.front().vl + f+gr[i%siz].dp.vl, q.front().how*gr[i%siz].dp.how);
add(gr[i%siz].dp.vl - f, gr[i%siz].dp.how);
f++;
}
}
else {
add(gr[0].dp.vl, gr[0].dp.how);
f++;
int k = siz / 2;
int qr = 1;
for (int i = 1; i < siz + k; ++i) {
if (qr > k)remove(gr[(i - k - 1 + siz) % siz].dp.how);
qr++;
ans += vt(q.front().vl + f+gr[i%siz].dp.vl, q.front().how*gr[i%siz].dp.how);
add(gr[i%siz].dp.vl - f, gr[i%siz].dp.how);
f++;
}
}
cout << ans.how << endl;
return 0;
}
Compilation message
shymbulak.cpp: In member function 'void graph::solve()':
shymbulak.cpp:160:49: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i <= len; ++i)if (used.size() == i)used.ad(0); else used[i] = 0;
^
shymbulak.cpp:170:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < road.size(); ++i) {
^
shymbulak.cpp:173:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < road.size(); ++i) {
^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:229:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < root.loop.size(); ++i) {
^
shymbulak.cpp: In member function 'void graph::read()':
shymbulak.cpp:78:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &len);
^
shymbulak.cpp:82:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &u, &v);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
42076 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
42076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
42340 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
42208 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
163 ms |
61480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
