| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 107307 | kuroni | Duathlon (APIO18_duathlon) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100005;
int n, m, u, v, nod, cnt = 0, sz[2 * N], sub[2 * N], num[N], low[N];
long long ans = 0;
bool vis[2 * N];
vector<int> st, com[N], adj[N], cut[2 * N];
vector<vector<int>> bi;
void process(vector<int> &ve)
{
sort(ve.begin(), ve.end());
ve.erase(unique(ve.begin(), ve.end()), ve.end());
++nod;
for (int &v : ve)
{
sz[nod]++;
com[v].push_back(nod);
}
}
void DFS(int u, int p = 0)
{
low[u] = num[u] = ++cnt;
for (int &v : adj[u])
if (v != p)
{
if (num[v] > 0)
low[u] = min(low[u], num[v]);
else
{
st.push_back(u);
DFS(v, u);
low[u] = min(low[u], low[v]);
if (low[v] >= num[u])
{
int v; bi.push_back({});
do
{
v = st.back(); st.pop_back();
bi.back().push_back(v);
} while (u != v);
process(bi.back());
}
}
}
st.push_back(u);
}
int get_subtree(int u, int p = 0)
{
sub[u] = sz[u];
for (int &v : cut[u])
if (v != p)
sub[u] += get_subtree(v, u);
return sub[u];
}
void find_ans(int u, int tot)
{
vis[u] = true;
int ver = com.size(), big = u > n;
ans += 1LL * sz[u] * (sz[u] - 1) * (ver * big + sz[u] - 2);
ans += 2LL * sz[u] * ((ver - 1) * big + sz[u] - 1) * (tot - sz[u]);
int cur = tot - sub[u];
for (int &v : cut[u])
if (!vis[v])
{
find_ans(v, tot);
ans += 2LL * cur * ((ver - 2) * big + sz[u]) * sub[v];
cur += sub[v];
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
nod = n;
while (m--)
{
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= n; i++)
if (num[i] == 0)
DFS(i);
for (int i = 1; i <= n; i++)
if (com[i].size() > 1)
{
sz[i] = 1;
for (int &v : com[i])
{
sz[v]--;
cut[i].push_back(v);
cut[v].push_back(i);
}
}
for (int i = 1; i <= nod; i++)
if (!vis[i])
find_ans(i, get_subtree(i));
for (int i = n + 1; i <= nod; i++)
{
int ver = cut[i].size();
ans += 1LL * ver * (sz[i] + ver - 1) * (sz[i] + ver - 2);
}
cout << ans;
}
st.push_back(u);
}
int get_subtree(int u, int p = 0)
{
sub[u] = sz[u];
for (int &v : cut[u])
if (v != p)
sub[u] += get_subtree(v, u);
return sub[u];
}
void find_ans(int u, int tot)
{
vis[u] = true;
int ver = com.size(), big = u > n;
ans += 1LL * sz[u] * (sz[u] - 1) * (ver * big + sz[u] - 2);
ans += 2LL * sz[u] * ((ver - 1) * big + sz[u] - 1) * (ot - sz[u]);
int cur = tot - sub[u];
for (int &v : cut[u])
if (!vis[v])
{
find_ans(v, tot);
ans += 2LL * cur * ((ver - 2) * big + sz[u]) * sub[v];
cur += sub[v];
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
nod = n;
while (m--)
{
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= n; i++)
if (num[i] == 0)
DFS(i);
for (int i = 1; i <= n; i++)
if (com[i].size() > 1)
{
sz[i] = 1;
for (int &v : com[i])
{
sz[v]--;
cut[i].push_back(v);
cut[v].push_back(i);
}
}
for (int i = 1; i <= nod; i++)
if (!vis[i])
find_ans(i, get_subtree(i));
for (int i = n + 1; i <= nod; i++)
{
int ver = cut[i].size();
ans += 1LL * ver * (sz[i] + ver - 1) * (sz[i] + ver - 2);
}
cout << ans;
}