oj.uz

Submission #926509

# Submission time Handle Problem Language Result Execution time Memory
926509 2024-02-13T07:34:19 Z codefox Duathlon (APIO18_duathlon) C++14
66 / 100
 157 ms 42576 KB 
#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<pii>> cgraph;
vector<vector<ll>> opt;
vector<vector<int>> neigh;
vector<int> neighsum;
vector<vector<int>> asso;
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);
    int sub = 0;
    int lastd = -1;
    for (int ele:graph[i])
    {
        if (ele == p) continue;
        if (!num[ele])
        {
            sub++;
            dfs(ele, i);
            if (low[ele]==num[i])
            {
                while(s.top() != ele)
                {
                    comp[s.top()] = d;
                    compsize[d]++;
                    asso[d].push_back(s.top());
                    s.pop();
                }
                comp[ele] = d;
                compsize[d]++;
                asso[d].push_back(ele);
                s.pop();
                lastd = d;
                d++;
            }
        }
        low[i] = min(low[i], low[ele]);
    }
    if (i==root && sub ==1 && lastd != -1)
    {
        art[lastd] = 1;
        compsize[lastd]++;
        comp[i] = lastd;
        s.pop();
        return;
    }
    if (num[i]==low[i])
    {
        art[d] = 1;
        while (s.top() != i)
        {
            comp[s.top()] = d;
            compsize[d]++;
            asso[d].push_back(s.top());
            s.pop();
        }
        asso[d].push_back(i);
        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 (pii ele2:cgraph[i])
    {
        int ele = ele2.second;
        if (vis[ele]) continue;
        dfs2(ele);
        neigh[ele2.first].push_back(opt[ele][0]);
        neighsum[ele2.first]+=opt[ele][0];
        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;
    }
    for (int ele:asso[i])
    {
        for (int ele2:neigh[ele])
        {
            if (!art[i]) sol -= ele2*(neighsum[ele]-ele2)*(compsize[i]);
            else sol -= ele2*(neighsum[ele]-ele2)*(compsize[i]-1);
        }
    }
}

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<pii>());
    neigh.assign(n, vector<int>());
    asso.assign(n, vector<int>());
    neighsum.assign(n, 0);
    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])
        {
            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({i, 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 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 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Incorrect 0 ms 348 KB Output isn't correct
23 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 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Incorrect 0 ms 348 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 35096 KB Output is correct
2 Correct 97 ms 35540 KB Output is correct
3 Correct 127 ms 35548 KB Output is correct
4 Correct 87 ms 34472 KB Output is correct
5 Correct 97 ms 31672 KB Output is correct
6 Correct 128 ms 34976 KB Output is correct
7 Correct 97 ms 33340 KB Output is correct
8 Correct 104 ms 33924 KB Output is correct
9 Correct 109 ms 32040 KB Output is correct
10 Correct 122 ms 31660 KB Output is correct
11 Correct 90 ms 29176 KB Output is correct
12 Correct 86 ms 29108 KB Output is correct
13 Correct 78 ms 29008 KB Output is correct
14 Correct 92 ms 28824 KB Output is correct
15 Correct 66 ms 28756 KB Output is correct
16 Correct 63 ms 28500 KB Output is correct
17 Correct 17 ms 23896 KB Output is correct
18 Correct 18 ms 23792 KB Output is correct
19 Correct 19 ms 23952 KB Output is correct
20 Correct 17 ms 23896 KB Output is correct
21 Correct 17 ms 23896 KB Output is correct
22 Correct 17 ms 24152 KB Output is correct

Subtask #4
10.0 / 10.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 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 860 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 600 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 600 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 109 ms 34640 KB Output is correct
2 Correct 127 ms 34476 KB Output is correct
3 Correct 117 ms 34640 KB Output is correct
4 Correct 106 ms 34668 KB Output is correct
5 Correct 120 ms 34640 KB Output is correct
6 Correct 140 ms 42576 KB Output is correct
7 Correct 121 ms 39804 KB Output is correct
8 Correct 120 ms 38480 KB Output is correct
9 Correct 152 ms 37196 KB Output is correct
10 Correct 116 ms 34572 KB Output is correct
11 Correct 107 ms 34552 KB Output is correct
12 Correct 132 ms 34484 KB Output is correct
13 Correct 133 ms 34584 KB Output is correct
14 Correct 114 ms 33844 KB Output is correct
15 Correct 101 ms 33108 KB Output is correct
16 Correct 70 ms 30216 KB Output is correct
17 Correct 92 ms 37288 KB Output is correct
18 Correct 96 ms 35924 KB Output is correct
19 Correct 96 ms 35644 KB Output is correct
20 Correct 123 ms 35080 KB Output is correct

Subtask #6
15.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 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 600 KB Output is correct
11 Correct 1 ms 668 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 600 KB Output is correct
16 Correct 1 ms 600 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
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 0 ms 604 KB Output is correct
27 Correct 0 ms 604 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 34644 KB Output is correct
2 Correct 127 ms 34864 KB Output is correct
3 Correct 123 ms 33876 KB Output is correct
4 Correct 157 ms 31908 KB Output is correct
5 Correct 95 ms 29136 KB Output is correct
6 Correct 89 ms 28116 KB Output is correct
7 Correct 87 ms 27436 KB Output is correct
8 Correct 79 ms 26464 KB Output is correct
9 Correct 89 ms 26140 KB Output is correct
10 Correct 78 ms 26204 KB Output is correct
11 Correct 81 ms 25680 KB Output is correct
12 Correct 82 ms 25388 KB Output is correct
13 Correct 79 ms 25224 KB Output is correct
14 Correct 80 ms 27572 KB Output is correct
15 Correct 140 ms 39504 KB Output is correct
16 Correct 143 ms 37572 KB Output is correct
17 Correct 125 ms 37560 KB Output is correct
18 Correct 154 ms 36108 KB Output is correct
19 Correct 122 ms 31884 KB Output is correct
20 Correct 117 ms 31980 KB Output is correct
21 Correct 116 ms 31840 KB Output is correct
22 Correct 121 ms 30368 KB Output is correct
23 Correct 93 ms 28340 KB Output is correct
24 Correct 112 ms 34128 KB Output is correct
25 Correct 110 ms 33868 KB Output is correct
26 Correct 129 ms 33788 KB Output is correct
27 Correct 110 ms 32740 KB Output is correct

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 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Incorrect 0 ms 348 KB Output isn't correct
23 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 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Incorrect 0 ms 348 KB Output isn't correct
23 Halted 0 ms 0 KB -