Submission #925308

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
925308	2024-02-11T11:24:55 Z	codefox	Duathlon (APIO18_duathlon)	C++14	31 / 100	100 ms	29180 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;
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])
            {
                while(s.top() != i)
                {
                    comp[s.top()] = d;
                    compsize[d]++;
                    s.pop();
                }
                d++;
            }
        }
        low[i] = min(low[i], low[ele]);
    }
    if (num[i]==low[i])
    {
        art[d] = 1;
        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]*(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])*(compsize[i]-1)*2;
        if (!art[i]) sol += opt[ele][0]*(compsize[i])*2;
        sol += opt[ele][1]*compsize[i]*2;
    }
    for (auto 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));
    
    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);
    }
    
    for (int i = 0; i < n; i++)
    {
        if (!num[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	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 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	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 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	26964 KB	Output is correct
2	Correct	78 ms	27032 KB	Output is correct
3	Correct	81 ms	25720 KB	Output is correct
4	Correct	78 ms	24916 KB	Output is correct
5	Correct	76 ms	23124 KB	Output is correct
6	Correct	82 ms	24684 KB	Output is correct
7	Correct	81 ms	22868 KB	Output is correct
8	Correct	82 ms	23380 KB	Output is correct
9	Correct	84 ms	21968 KB	Output is correct
10	Correct	96 ms	21764 KB	Output is correct
11	Correct	77 ms	20564 KB	Output is correct
12	Correct	71 ms	20276 KB	Output is correct
13	Correct	66 ms	20564 KB	Output is correct
14	Correct	78 ms	20228 KB	Output is correct
15	Correct	54 ms	20060 KB	Output is correct
16	Correct	54 ms	19792 KB	Output is correct
17	Correct	11 ms	15196 KB	Output is correct
18	Correct	12 ms	15196 KB	Output is correct
19	Correct	11 ms	15196 KB	Output is correct
20	Correct	11 ms	15196 KB	Output is correct
21	Correct	12 ms	15152 KB	Output is correct
22	Correct	11 ms	15196 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	600 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	600 KB	Output is correct
11	Correct	1 ms	600 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	604 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	604 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	90 ms	22660 KB	Output is correct
2	Correct	86 ms	22712 KB	Output is correct
3	Correct	98 ms	22728 KB	Output is correct
4	Correct	89 ms	22608 KB	Output is correct
5	Correct	91 ms	22568 KB	Output is correct
6	Correct	94 ms	29180 KB	Output is correct
7	Correct	100 ms	27604 KB	Output is correct
8	Correct	95 ms	26192 KB	Output is correct
9	Correct	97 ms	25168 KB	Output is correct
10	Correct	89 ms	22596 KB	Output is correct
11	Correct	88 ms	22668 KB	Output is correct
12	Correct	99 ms	23100 KB	Output is correct
13	Correct	86 ms	22612 KB	Output is correct
14	Correct	81 ms	22312 KB	Output is correct
15	Correct	72 ms	21840 KB	Output is correct
16	Correct	50 ms	20048 KB	Output is correct
17	Correct	86 ms	25144 KB	Output is correct
18	Correct	79 ms	25288 KB	Output is correct
19	Correct	77 ms	25140 KB	Output is correct
20	Correct	74 ms	24708 KB	Output is correct

Subtask #6
0 / 15.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	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	95 ms	22628 KB	Output is correct
2	Correct	95 ms	22352 KB	Output is correct
3	Incorrect	96 ms	22356 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 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	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 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 #925308

Compilation message