| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 500081 | kaxzert | Duathlon (APIO18_duathlon) | C++17 | 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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;
vi ADJ[2*MX];
int n,m,totsz[2*MX];
void ad(int a, int b) {
ADJ[a].pb(b), ADJ[b].pb(a);
}
template<int SZ> struct BCC {
int N, ti = 0;
vi adj[SZ];
int disc[SZ], low[SZ], comp[SZ], par[SZ];
vector<vpi> fin;
int compsz[SZ];
vpi st;
void addEdge(int u, int v) {
adj[u].pb(v), adj[v].pb(u);
}
void BCCutil(int u, bool root = 0) {
disc[u] = low[u] = ti++;
int child = 0;
for (int i: adj[u]) if (i != par[u]) {
if (disc[i] == -1) {
child ++; par[i] = u;
st.pb({u,i});
BCCutil(i);
low[u] = min(low[u],low[i]);
if ((root && child > 1) || (!root && disc[u] <= low[i])) { // articulation point!
vpi tmp;
while (st.back() != mp(u,i)) tmp.pb(st.back()), st.pop_back();
tmp.pb(st.back()), st.pop_back();
fin.pb(tmp);
}
} else if (disc[i] < disc[u]) {
low[u] = min(low[u],disc[i]);
st.pb({u,i});
}
}
}
void bcc() {
FOR(i,1,N+1) par[i] = disc[i] = low[i] = -1;
FOR(i,1,N+1) if (disc[i] == -1) {
BCCutil(i,1);
if (sz(st)) fin.pb(st);
st.clear();
}
int co = 0;
for (auto a: fin) {
set<int> s;
for (auto b: a) s.insert(b.f), s.insert(b.s);
co ++;
compsz[co] = sz(s);
for (int i: s) ad(i,n+co);
}
}
};
ll ans = 0;
BCC<MX> B;
bool visit[2*MX];
void dfs1(int x, int y = 0) {
visit[x] = 1; if (x <= n) totsz[x] = 1;
for (int i: ADJ[x]) if (i != y) {
dfs1(i,x);
totsz[x] += totsz[i];
}
}
void dfs2(int x, int p, int y = 0) {
if (x <= n) {
for (int i: ADJ[x]) {
assert(i > n);
if (i != y) {
ans -= (ll)(B.compsz[i-n]-1)*(totsz[p]-totsz[i])*(totsz[p]-totsz[i]-1);
} else {
ans -= (ll)(B.compsz[i-n]-1)*totsz[x]*(totsz[x]-1);
}
}
}
for (int i: ADJ[x]) if (i != y) dfs2(i,p,x);
}
void init() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
F0R(i,m) {
int a,b; cin >> a >> b;
B.addEdge(a,b);
}
B.N = n;
B.bcc();
}
void genTree() {
FOR(i,1,n+1) if (!visit[i]) {
dfs1(i);
ans += (ll)totsz[i]*(totsz[i]-1)*(totsz[i]-2);
// cout << i << " " << totsz[i] << "\n";
dfs2(i,i);
}
}
int main() {
init();
genTree();
cout << ans;
}
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/