Submission #925296

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
925296	2024-02-11T11:05:34 Z	codefox	Duathlon (APIO18_duathlon)	C++14	31 / 100	163 ms	32504 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])
            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;
        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]*(compsize[i]-1);
    sol += (compsize[i]-1)*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]);
        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]) 
        {
            c = 0;
            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]);
            cgraph[comp[ele]].push_back(comp[i]);
        }
    }
    
    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	348 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	1 ms	600 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	348 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	1 ms	600 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	82 ms	26964 KB	Output is correct
2	Correct	83 ms	26992 KB	Output is correct
3	Correct	88 ms	26708 KB	Output is correct
4	Correct	80 ms	26876 KB	Output is correct
5	Correct	82 ms	25172 KB	Output is correct
6	Correct	105 ms	27120 KB	Output is correct
7	Correct	88 ms	25424 KB	Output is correct
8	Correct	96 ms	25892 KB	Output is correct
9	Correct	113 ms	24264 KB	Output is correct
10	Correct	101 ms	24144 KB	Output is correct
11	Correct	79 ms	22612 KB	Output is correct
12	Correct	87 ms	22300 KB	Output is correct
13	Correct	73 ms	22296 KB	Output is correct
14	Correct	72 ms	21984 KB	Output is correct
15	Correct	69 ms	20984 KB	Output is correct
16	Correct	70 ms	20816 KB	Output is correct
17	Correct	16 ms	15196 KB	Output is correct
18	Correct	15 ms	15196 KB	Output is correct
19	Correct	11 ms	15192 KB	Output is correct
20	Correct	12 ms	15196 KB	Output is correct
21	Correct	11 ms	15196 KB	Output is correct
22	Correct	12 ms	15224 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	600 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	440 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	600 KB	Output is correct
18	Correct	1 ms	600 KB	Output is correct
19	Correct	1 ms	600 KB	Output is correct
20	Correct	2 ms	860 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	109 ms	24240 KB	Output is correct
2	Correct	104 ms	25684 KB	Output is correct
3	Correct	98 ms	25428 KB	Output is correct
4	Correct	117 ms	25428 KB	Output is correct
5	Correct	105 ms	25572 KB	Output is correct
6	Correct	106 ms	32504 KB	Output is correct
7	Correct	163 ms	30612 KB	Output is correct
8	Correct	109 ms	29268 KB	Output is correct
9	Correct	109 ms	28196 KB	Output is correct
10	Correct	103 ms	25472 KB	Output is correct
11	Correct	118 ms	25632 KB	Output is correct
12	Correct	100 ms	25680 KB	Output is correct
13	Correct	107 ms	25684 KB	Output is correct
14	Correct	106 ms	24856 KB	Output is correct
15	Correct	102 ms	23956 KB	Output is correct
16	Correct	56 ms	21076 KB	Output is correct
17	Correct	89 ms	28104 KB	Output is correct
18	Correct	87 ms	27708 KB	Output is correct
19	Correct	103 ms	27308 KB	Output is correct
20	Correct	87 ms	26500 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	600 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	104 ms	24404 KB	Output is correct
2	Correct	109 ms	25588 KB	Output is correct
3	Incorrect	138 ms	25936 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	348 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	1 ms	600 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	348 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	1 ms	600 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 #925296

Compilation message