Submission #925300

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
925300	2024-02-11T11:13:33 Z	codefox	Duathlon (APIO18_duathlon)	C++14	31 / 100	132 ms	31232 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])*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]) 
        {
            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	344 KB	Output is correct
2	Correct	1 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	348 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Incorrect	1 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	1 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	348 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Incorrect	1 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	78 ms	26848 KB	Output is correct
2	Correct	75 ms	26964 KB	Output is correct
3	Correct	90 ms	26704 KB	Output is correct
4	Correct	83 ms	25628 KB	Output is correct
5	Correct	88 ms	23724 KB	Output is correct
6	Correct	89 ms	25936 KB	Output is correct
7	Correct	91 ms	24148 KB	Output is correct
8	Correct	88 ms	24500 KB	Output is correct
9	Correct	120 ms	22848 KB	Output is correct
10	Correct	85 ms	22792 KB	Output is correct
11	Correct	87 ms	21588 KB	Output is correct
12	Correct	73 ms	21348 KB	Output is correct
13	Correct	74 ms	21328 KB	Output is correct
14	Correct	71 ms	21184 KB	Output is correct
15	Correct	58 ms	20312 KB	Output is correct
16	Correct	60 ms	20124 KB	Output is correct
17	Correct	14 ms	15192 KB	Output is correct
18	Correct	12 ms	15196 KB	Output is correct
19	Correct	11 ms	15156 KB	Output is correct
20	Correct	11 ms	15196 KB	Output is correct
21	Correct	11 ms	15196 KB	Output is correct
22	Correct	15 ms	15452 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 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	600 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	2 ms	600 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	600 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	24204 KB	Output is correct
2	Correct	97 ms	24404 KB	Output is correct
3	Correct	102 ms	24420 KB	Output is correct
4	Correct	123 ms	24404 KB	Output is correct
5	Correct	99 ms	24368 KB	Output is correct
6	Correct	110 ms	31232 KB	Output is correct
7	Correct	117 ms	29412 KB	Output is correct
8	Correct	112 ms	28244 KB	Output is correct
9	Correct	103 ms	26964 KB	Output is correct
10	Correct	100 ms	24404 KB	Output is correct
11	Correct	132 ms	24260 KB	Output is correct
12	Correct	107 ms	24400 KB	Output is correct
13	Correct	98 ms	24400 KB	Output is correct
14	Correct	91 ms	23752 KB	Output is correct
15	Correct	81 ms	22960 KB	Output is correct
16	Correct	66 ms	20820 KB	Output is correct
17	Correct	88 ms	26816 KB	Output is correct
18	Correct	89 ms	26396 KB	Output is correct
19	Correct	85 ms	26028 KB	Output is correct
20	Correct	91 ms	25220 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	104 ms	24404 KB	Output is correct
2	Correct	124 ms	24384 KB	Output is correct
3	Incorrect	117 ms	24436 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	1 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	348 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Incorrect	1 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	1 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	348 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Incorrect	1 ms	348 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Submission #925300

Compilation message