Submission #460058

#	Time	Username	Problem	Language	Result	Execution time	Memory
460058		Killer2501	Duathlon (APIO18_duathlon)	C++14	100 / 100	188 ms	30664 KiB

count_triplets

#include<bits/stdc++.h>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define pii pair<ll, pll>
using namespace std;
using ll = long long;
const int  N = 2e5+55;
const ll mod = 1e9+7;
const ll mod1 = 1e9+1;
const ll base = 311;
const ll base1 = 331;
ll m, n, t, k, a[N], tong, b[N], dp[N], c[N], lab[N], cnt, ans, h[N], d[N], num[N], low[N];
priority_queue< pll, vector<pll>, greater<pll> > pq;
string s;
vector<ll> adj[N], g[N], kq;
vector<pll> e;
ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n & 1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}
void dfs(ll u, ll p)
{
    num[u] = low[u] = ++k;
    ++tong;
    kq.pb(u);
    for(ll v : adj[u])
    {
        if(v == p)continue;
        if(num[v])low[u] = min(low[u], num[v]);
        else
        {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] >= num[u])
            {
                ++cnt;
                g[u].pb(cnt+n);
                while(g[cnt+n].empty() || g[cnt+n].back() != v)
                {
                    g[cnt+n].pb(kq.back());
                    kq.pop_back();
                }
            }
        }
    }
}
void dfs1(ll u, ll p)
{
    d[u] = (u <= n);
    for(ll v : g[u])
    {
        dfs1(v, u);
        d[u] += d[v];
        if(u > n)ans -= g[u].size() * d[v] * (d[v] - 1);
    }
    if(u > n)ans -= (tong - d[u]) * (tong - d[u] - 1) * g[u].size();
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i ++)
    {
        ll x, y;
        cin >> x >> y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    for(int i = 1; i <= n; i ++)
    {
        if(!num[i])
        {
            tong = 0;
            dfs(i, 0);
            ans += tong * (tong - 1) * (tong - 2);
            dfs1(i, 0);
        }
    }
    cout << ans;
}
/*
3 5
12345678
000
0??
1?0
?11
???
*/

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 15 / 15
• Subtask 7: 20 / 20
• Subtask 8: 8 / 8
• Subtask 9: 10 / 10