Submission #926202

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
926202	2024-02-12T17:11:07 Z	codefox	Duathlon (APIO18_duathlon)	C++14	31 / 100	106 ms	29952 KB

count_triplets

#include<bits/stdc++.h>
    
using namespace std;
    
#define int ll    
#define ll long long
#define pii pair<int, int>
    
vector<vector<int>> graph;
vector<vector<int>> cgraph;
vector<vector<ll>> opt;
vector<int> comp;
vector<int> low;
vector<int> num;
vector<int> vis;
vector<int> art;
vector<ll> compsize;
stack<int> s;
int root = -1;
ll sol = 0;
int c = 0;
int d = 0;
ll n, m;
    
void dfs(int i, int p)
{
    num[i] = low[i] = ++c;
    s.push(i);
    for (int ele:graph[i])
    {
        if (ele == p) continue;
        if (!num[ele]) 
        {
            dfs(ele, i);
            if (low[ele]==num[i] && i != root)
            {
                while(s.top() != ele)
                {
                    comp[s.top()] = d;
                    compsize[d]++;
                    s.pop();
                }
                comp[ele] = d;
                compsize[d]++;
                s.pop();
                d++;
            }
        }
        low[i] = min(low[i], low[ele]);
    }
    if (num[i]==low[i])
    {
        art[d] = 1;
        while (s.top() != i)
        {
            comp[s.top()] = d;
            compsize[d]++;
            s.pop();
        }
        comp[i] = d;
        compsize[d]++;
        s.pop();
        d++;
    }
}
    
void dfs2(int i)
{
    vis[i] = 1;
    opt[i][0] = compsize[i];
    opt[i][1] = (compsize[i]-1)*(compsize[i]-2) +compsize[i]-1;
    if (!art[i]) opt[i][1] += compsize[i]-1;
 
    sol += (compsize[i]-2)*compsize[i]*(compsize[i]-1);
    if (!art[i]) sol += compsize[i]*(compsize[i]-1);
    vector<array<ll, 2>> ones;
    ll sum = 0;
    for (int ele:cgraph[i])
    {
        if (vis[ele]) continue;
        dfs2(ele);
        opt[i][0] += opt[ele][0];
        opt[i][1] += opt[ele][1] + opt[ele][0]*compsize[i];
        sum += opt[ele][0];
        ones.push_back({opt[ele][0], opt[ele][1]});
        sol += opt[ele][0]*(compsize[i]-1)*(compsize[i]-2)*2;
        sol += opt[ele][0]*(compsize[i]-1)*2;
        if (!art[i]) sol += opt[ele][0]*(compsize[i]-1)*2;
        sol += opt[ele][1]*compsize[i]*2;
    }
 
    for (array<ll, 2> ele:ones)
    {
        if (!art[i]) sol += ele[0]*(sum-ele[0])*(compsize[i]+1);
        else         sol += ele[0]*(sum-ele[0])*(compsize[i]);
        sol += ele[1]*(sum-ele[0])*2;
    }
}
    
int32_t main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    
    cin >> n >> m;
    graph.assign(n, vector<int>());
    cgraph.assign(n, vector<int>());
    compsize.assign(n, 0);
    low.assign(n, 0);
    num.assign(n, 0);
    comp.assign(n, -1);
    vis.assign(n, 0);
    art.assign(n, 0);
    opt.assign(n, vector<ll>(2, 0));

    vector<int> degree(n, 0);
    for (int i =0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
        degree[a]++;
        degree[b]++;
    }
    
    for (int i =0; i < n; i++)
    {
        if (!num[i]) 
        {
            root = i;
            dfs(i, -1);
        }
    }
    
    for (int i = 0; i <n; i++)
    {
        for (int ele:graph[i])
        {
            if (comp[i] == comp[ele]) continue;
            cgraph[comp[i]].push_back(comp[ele]);
        }
    }
    
    for (int i = 0; i< n; i++)
    {
        if (!vis[comp[i]])
        {
            dfs2(comp[i]);
        }
    }

    cout << sol << "\n";
    
    return 0;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Incorrect	0 ms	348 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Incorrect	0 ms	348 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	75 ms	27728 KB	Output is correct
2	Correct	89 ms	27940 KB	Output is correct
3	Correct	84 ms	26568 KB	Output is correct
4	Correct	74 ms	25684 KB	Output is correct
5	Correct	100 ms	23892 KB	Output is correct
6	Correct	95 ms	25408 KB	Output is correct
7	Correct	86 ms	23792 KB	Output is correct
8	Correct	81 ms	24168 KB	Output is correct
9	Correct	85 ms	22352 KB	Output is correct
10	Correct	89 ms	22528 KB	Output is correct
11	Correct	68 ms	20808 KB	Output is correct
12	Correct	68 ms	20584 KB	Output is correct
13	Correct	81 ms	20644 KB	Output is correct
14	Correct	62 ms	20496 KB	Output is correct
15	Correct	52 ms	20304 KB	Output is correct
16	Correct	53 ms	20052 KB	Output is correct
17	Correct	12 ms	15964 KB	Output is correct
18	Correct	12 ms	15964 KB	Output is correct
19	Correct	11 ms	15964 KB	Output is correct
20	Correct	11 ms	15964 KB	Output is correct
21	Correct	11 ms	16116 KB	Output is correct
22	Correct	13 ms	15964 KB	Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	87 ms	23520 KB	Output is correct
2	Correct	104 ms	23592 KB	Output is correct
3	Correct	106 ms	23448 KB	Output is correct
4	Correct	84 ms	23376 KB	Output is correct
5	Correct	87 ms	23408 KB	Output is correct
6	Correct	94 ms	29952 KB	Output is correct
7	Correct	105 ms	28552 KB	Output is correct
8	Correct	93 ms	27472 KB	Output is correct
9	Correct	94 ms	25952 KB	Output is correct
10	Correct	91 ms	23584 KB	Output is correct
11	Correct	86 ms	23460 KB	Output is correct
12	Correct	86 ms	23460 KB	Output is correct
13	Correct	96 ms	23584 KB	Output is correct
14	Correct	80 ms	23124 KB	Output is correct
15	Correct	71 ms	22612 KB	Output is correct
16	Correct	61 ms	20816 KB	Output is correct
17	Correct	75 ms	26096 KB	Output is correct
18	Correct	74 ms	26048 KB	Output is correct
19	Correct	78 ms	25788 KB	Output is correct
20	Correct	76 ms	25320 KB	Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	90 ms	23376 KB	Output is correct
2	Correct	93 ms	23336 KB	Output is correct
3	Incorrect	101 ms	23084 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Incorrect	0 ms	348 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Incorrect	0 ms	348 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Submission #926202

Compilation message