oj.uz

Submission #926194

# Submission time Handle Problem Language Result Execution time Memory
926194 2024-02-12T17:05:03 Z codefox Duathlon (APIO18_duathlon) C++14
31 / 100
 122 ms 37916 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<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])
            {
                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, int p)
{
    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, i);
        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]++;
    }
    
    vector<pii> nodes;
    for (int i= 0; i < n; i++) nodes.push_back({degree[i], i});

    sort(nodes.begin(), nodes.end());
    for (pii ele:nodes)
    {
        if (!num[ele.second]) 
        {
            dfs(ele.second, -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 (pii ele:nodes)
    {
        if (!vis[comp[ele.second]])
        {
            dfs2(comp[ele.second], -1);
        }
    }

    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 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 344 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 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 344 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 113 ms 29324 KB Output is correct
2 Correct 76 ms 29380 KB Output is correct
3 Correct 122 ms 29268 KB Output is correct
4 Correct 87 ms 27332 KB Output is correct
5 Correct 81 ms 26468 KB Output is correct
6 Correct 88 ms 31424 KB Output is correct
7 Correct 87 ms 26608 KB Output is correct
8 Correct 98 ms 29008 KB Output is correct
9 Correct 95 ms 25284 KB Output is correct
10 Correct 86 ms 25792 KB Output is correct
11 Correct 78 ms 24028 KB Output is correct
12 Correct 109 ms 23828 KB Output is correct
13 Correct 80 ms 24004 KB Output is correct
14 Correct 74 ms 23664 KB Output is correct
15 Correct 60 ms 22980 KB Output is correct
16 Correct 62 ms 22724 KB Output is correct
17 Correct 20 ms 18132 KB Output is correct
18 Correct 20 ms 18128 KB Output is correct
19 Correct 20 ms 18128 KB Output is correct
20 Correct 20 ms 18132 KB Output is correct
21 Correct 21 ms 18132 KB Output is correct
22 Correct 21 ms 18132 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 2 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 696 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 704 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 696 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 102 ms 25028 KB Output is correct
2 Correct 95 ms 24968 KB Output is correct
3 Correct 99 ms 25116 KB Output is correct
4 Correct 101 ms 25028 KB Output is correct
5 Correct 97 ms 25124 KB Output is correct
6 Correct 118 ms 37916 KB Output is correct
7 Correct 109 ms 33788 KB Output is correct
8 Correct 106 ms 28612 KB Output is correct
9 Correct 100 ms 27332 KB Output is correct
10 Correct 96 ms 25024 KB Output is correct
11 Correct 95 ms 25028 KB Output is correct
12 Correct 115 ms 25104 KB Output is correct
13 Correct 94 ms 25024 KB Output is correct
14 Correct 88 ms 25788 KB Output is correct
15 Correct 84 ms 25076 KB Output is correct
16 Correct 59 ms 22984 KB Output is correct
17 Correct 88 ms 29764 KB Output is correct
18 Correct 92 ms 29356 KB Output is correct
19 Correct 99 ms 29488 KB Output is correct
20 Correct 87 ms 28600 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 97 ms 25028 KB Output is correct
2 Correct 116 ms 24804 KB Output is correct
3 Incorrect 109 ms 24572 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 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 344 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 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 344 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -