Submission #771628

#	Time	Username	Problem	Language	Result	Execution time	Memory
771628		SamAnd	철인 이종 경기 (APIO18_duathlon)	C++17	100 / 100	169 ms	38640 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 400005;

int n, m;
vector<vector<int> > adj;

vector<bool> visited;
vector<int> tin, low;
int timer;

vector<pair<int, int> > s;
vector<vector<pair<int, int> > > v;
void dfs(int v, int p = -1) {
    visited[v] = true;
    tin[v] = low[v] = timer++;
    int children=0;
    for (int to : adj[v]) {
        if (to == p) continue;
        if (visited[to]) {
            low[v] = min(low[v], tin[to]);
            if (tin[to] < tin[v])
                s.push_back(m_p(v, to));
        } else {
            ++children;
            s.push_back(m_p(v, to));
            dfs(to, v);
            low[v] = min(low[v], low[to]);
            if ((low[to] >= tin[v] && p != -1) || (p == -1 && children > 1))
            {
                vector<pair<int, int> > vv;
                while (s.back() != m_p(v, to))
                {
                    vv.push_back(s.back());
                    s.pop_back();
                }
                vv.push_back(s.back());
                s.pop_back();
                ::v.push_back(vv);
            }
        }
    }
}

void find_cutpoints() {
    timer = 0;
    visited.assign(n, false);
    tin.assign(n, -1);
    low.assign(n, -1);
    for (int i = 0; i < n; ++i) {
        if (!visited[i])
        {
            dfs (i);
            if (!s.empty())
            {
                v.push_back(s);
                s.clear();
            }
        }
    }
}

vector<int> g[N];

int q[N];
void dfs1(int x, int p)
{
    if (x < n)
        q[x] = 1;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (h == p)
            continue;
        dfs1(h, x);
        q[x] += q[h];
    }
}

ll ans;
void dfs2(int x, int p, int r)
{
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (h == p)
            continue;
        dfs2(h, x, r);
    }

    if (x >= n)
    {
        for (int i = 0; i < g[x].size(); ++i)
        {
            int h = g[x][i];
            int qq;
            if (h == p)
                qq = (q[r] - q[x]);
            else
                qq = q[h];
            ans -= qq * 1LL * (qq - 1) * 1LL * (sz(g[x]) - 1);
        }
    }
}

void solv()
{
    cin >> n >> m;
    adj.assign(n, {});
    for (int i = 0; i < m; ++i)
    {
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    find_cutpoints();

    int k = n;
    for (int i = 0; i < sz(v); ++i)
    {
        set<int> s;
        for (int j = 0; j < sz(v[i]); ++j)
        {
            s.insert(v[i][j].fi);
            s.insert(v[i][j].se);
        }
        for (auto it = s.begin(); it != s.end(); ++it)
        {
            g[*it].push_back(k);
            g[k].push_back(*it);
        }
        k++;
    }

    for (int i = 0; i < k; ++i)
    {
        if (!q[i])
        {
            dfs1(i, i);
            ans += (q[i] * 1LL * (q[i] - 1) * 1LL * (q[i] - 2));
            dfs2(i, i, i);
        }
    }

    cout << ans << "\n";
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solv();
    }
    return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'void dfs1(int, int)':
count_triplets.cpp:78:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs2(int, int, int)':
count_triplets.cpp:91:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
count_triplets.cpp:101:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for (int i = 0; i < g[x].size(); ++i)
      |                         ~~^~~~~~~~~~~~~

• 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