Submission #107377

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
107377	2019-04-23T14:12:53 Z	kuroni	Duathlon (APIO18_duathlon)	C++14	31 / 100	370 ms	33068 KB

count_triplets

#include <iostream>
#include <cstdio>
#include <vector>
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];
    
void DFS(int u, int p = 0)
{
    low[u] = num[u] = ++cnt;
    st.push_back(u);
    for (int &v : adj[u])
        if (v != p)
        {
            if (num[v] > 0)
                low[u] = min(low[u], num[v]);
            else
            {
                DFS(v, u);
                low[u] = min(low[u], low[v]);
                if (low[v] >= num[u])
                {
                    ++nod;
                    int v;
                    do
                    {
                        v = st.back(); st.pop_back();
                        sz[nod]++;
                        com[v].push_back(nod);
                    } while (u != v);
                    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;
    int ver = cut[u].size(), big = u > n;
    ans += 1LL * sz[u] * (sz[u] - 1) * (ver * big + sz[u] - 2);
    ans += 2LL * sz[u] * ((ver - 1) * big + 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 * ((ver - 2) * big + 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 (!vis[i])
            find_ans(i, get_subtree(i));
    cout << ans;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	9700 KB	Output is correct
2	Correct	12 ms	9728 KB	Output is correct
3	Correct	12 ms	9728 KB	Output is correct
4	Correct	12 ms	9728 KB	Output is correct
5	Correct	13 ms	9700 KB	Output is correct
6	Correct	10 ms	9728 KB	Output is correct
7	Incorrect	11 ms	9728 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	9700 KB	Output is correct
2	Correct	12 ms	9728 KB	Output is correct
3	Correct	12 ms	9728 KB	Output is correct
4	Correct	12 ms	9728 KB	Output is correct
5	Correct	13 ms	9700 KB	Output is correct
6	Correct	10 ms	9728 KB	Output is correct
7	Incorrect	11 ms	9728 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #3
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	154 ms	25072 KB	Output is correct
2	Correct	146 ms	25232 KB	Output is correct
3	Correct	244 ms	27892 KB	Output is correct
4	Correct	180 ms	25708 KB	Output is correct
5	Correct	208 ms	24820 KB	Output is correct
6	Correct	282 ms	27252 KB	Output is correct
7	Correct	299 ms	25776 KB	Output is correct
8	Correct	226 ms	26104 KB	Output is correct
9	Correct	241 ms	24452 KB	Output is correct
10	Correct	215 ms	24312 KB	Output is correct
11	Correct	147 ms	21112 KB	Output is correct
12	Correct	132 ms	20884 KB	Output is correct
13	Correct	107 ms	20312 KB	Output is correct
14	Correct	164 ms	20268 KB	Output is correct
15	Correct	109 ms	18548 KB	Output is correct
16	Correct	106 ms	18420 KB	Output is correct
17	Correct	17 ms	11524 KB	Output is correct
18	Correct	14 ms	11652 KB	Output is correct
19	Correct	15 ms	11524 KB	Output is correct
20	Correct	17 ms	11524 KB	Output is correct
21	Correct	16 ms	11516 KB	Output is correct
22	Correct	18 ms	11516 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	9856 KB	Output is correct
2	Correct	12 ms	9856 KB	Output is correct
3	Correct	13 ms	9856 KB	Output is correct
4	Correct	15 ms	9984 KB	Output is correct
5	Correct	14 ms	9984 KB	Output is correct
6	Correct	13 ms	9984 KB	Output is correct
7	Correct	13 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	12 ms	9856 KB	Output is correct
11	Correct	11 ms	9828 KB	Output is correct
12	Correct	13 ms	9984 KB	Output is correct
13	Correct	14 ms	9984 KB	Output is correct
14	Correct	12 ms	9856 KB	Output is correct
15	Correct	13 ms	9856 KB	Output is correct
16	Correct	15 ms	9984 KB	Output is correct
17	Correct	12 ms	9856 KB	Output is correct
18	Correct	15 ms	9856 KB	Output is correct
19	Correct	10 ms	9856 KB	Output is correct
20	Correct	11 ms	9856 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	277 ms	24628 KB	Output is correct
2	Correct	264 ms	24824 KB	Output is correct
3	Correct	243 ms	24908 KB	Output is correct
4	Correct	257 ms	24952 KB	Output is correct
5	Correct	255 ms	24952 KB	Output is correct
6	Correct	370 ms	33068 KB	Output is correct
7	Correct	290 ms	29940 KB	Output is correct
8	Correct	258 ms	29384 KB	Output is correct
9	Correct	319 ms	27888 KB	Output is correct
10	Correct	197 ms	24812 KB	Output is correct
11	Correct	189 ms	24824 KB	Output is correct
12	Correct	223 ms	24828 KB	Output is correct
13	Correct	190 ms	24952 KB	Output is correct
14	Correct	185 ms	24100 KB	Output is correct
15	Correct	148 ms	23032 KB	Output is correct
16	Correct	88 ms	19188 KB	Output is correct
17	Correct	105 ms	23768 KB	Output is correct
18	Correct	104 ms	23664 KB	Output is correct
19	Correct	136 ms	23788 KB	Output is correct
20	Correct	135 ms	23740 KB	Output is correct

Subtask #6
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	9856 KB	Output is correct
2	Correct	14 ms	9988 KB	Output is correct
3	Incorrect	10 ms	9828 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	275 ms	24652 KB	Output is correct
2	Correct	274 ms	25036 KB	Output is correct
3	Incorrect	326 ms	24424 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	9700 KB	Output is correct
2	Correct	12 ms	9728 KB	Output is correct
3	Correct	12 ms	9728 KB	Output is correct
4	Correct	12 ms	9728 KB	Output is correct
5	Correct	13 ms	9700 KB	Output is correct
6	Correct	10 ms	9728 KB	Output is correct
7	Incorrect	11 ms	9728 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	9700 KB	Output is correct
2	Correct	12 ms	9728 KB	Output is correct
3	Correct	12 ms	9728 KB	Output is correct
4	Correct	12 ms	9728 KB	Output is correct
5	Correct	13 ms	9700 KB	Output is correct
6	Correct	10 ms	9728 KB	Output is correct
7	Incorrect	11 ms	9728 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Submission #107377

Compilation message