oj.uz

답안 #771622

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
771622 2023-07-03T07:30:25 Z SamAnd 철인 이종 경기 (APIO18_duathlon) C++17
0 / 100
 568 ms 1048576 KB 
#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 {
            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);
            }
            ++children;
        }
    }
}

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);
        }
    }
}

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

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

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 568 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 568 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 39876 KB Output is correct
2 Correct 93 ms 39956 KB Output is correct
3 Runtime error 528 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 9960 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 99 ms 29944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 9812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 29900 KB Output is correct
2 Incorrect 102 ms 29872 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 568 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 568 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -