oj.uz

Submission #107291

# Submission time Handle Problem Language Result Execution time Memory
107291 2019-04-23T06:55:21 Z kuroni Duathlon (APIO18_duathlon) C++14
23 / 100
 459 ms 37164 KB 
#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;
    ans += 1LL * sz[u] * (sz[u] - 1) * (sz[u] - 2);
    ans += 2LL * sz[u] * (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 * 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 (!cut[i].empty() && !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;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 9728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 9728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 165 ms 27416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 9984 KB Output is correct
2 Correct 12 ms 9984 KB Output is correct
3 Correct 13 ms 9984 KB Output is correct
4 Correct 13 ms 9984 KB Output is correct
5 Correct 13 ms 9984 KB Output is correct
6 Correct 15 ms 9984 KB Output is correct
7 Correct 12 ms 9984 KB Output is correct
8 Correct 15 ms 9984 KB Output is correct
9 Correct 13 ms 9984 KB Output is correct
10 Correct 14 ms 9984 KB Output is correct
11 Correct 13 ms 10032 KB Output is correct
12 Correct 13 ms 9984 KB Output is correct
13 Correct 12 ms 9984 KB Output is correct
14 Correct 13 ms 9984 KB Output is correct
15 Correct 13 ms 9984 KB Output is correct
16 Correct 11 ms 9856 KB Output is correct
17 Correct 13 ms 9984 KB Output is correct
18 Correct 12 ms 9984 KB Output is correct
19 Correct 11 ms 9984 KB Output is correct
20 Correct 13 ms 9984 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 30116 KB Output is correct
2 Correct 287 ms 30336 KB Output is correct
3 Correct 287 ms 30368 KB Output is correct
4 Correct 341 ms 30372 KB Output is correct
5 Correct 322 ms 30696 KB Output is correct
6 Correct 404 ms 37164 KB Output is correct
7 Correct 459 ms 34408 KB Output is correct
8 Correct 397 ms 34116 KB Output is correct
9 Correct 401 ms 32752 KB Output is correct
10 Correct 307 ms 30280 KB Output is correct
11 Correct 288 ms 30368 KB Output is correct
12 Correct 282 ms 30292 KB Output is correct
13 Correct 279 ms 30372 KB Output is correct
14 Correct 273 ms 28972 KB Output is correct
15 Correct 244 ms 27548 KB Output is correct
16 Correct 133 ms 21932 KB Output is correct
17 Correct 161 ms 28988 KB Output is correct
18 Correct 178 ms 28804 KB Output is correct
19 Correct 181 ms 28924 KB Output is correct
20 Correct 178 ms 28968 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9984 KB Output is correct
2 Correct 13 ms 9984 KB Output is correct
3 Incorrect 15 ms 9984 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 30200 KB Output is correct
2 Correct 309 ms 30568 KB Output is correct
3 Incorrect 290 ms 28960 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 9728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 9728 KB Output isn't correct
2 Halted 0 ms 0 KB -