oj.uz

Submission #924351

# Submission time Handle Problem Language Result Execution time Memory
924351 2024-02-08T21:28:43 Z codefox Duathlon (APIO18_duathlon) C++14
31 / 100
 155 ms 57648 KB 
#include<bits/stdc++.h>
    
using namespace std;
    
#define int ll    
#define ll long long
    
vector<vector<int>> graph;
vector<vector<int>> cgraph;
vector<int> comp;
vector<int> art;
vector<int> low;
vector<int> num;
vector<int> vis;
stack<int> s;
int c = 0;
int d = 0;
int root = 0;
int sub = 0;
vector<int> subtree;
vector<ll> compsize;
ll sol = 0;
ll n, m;
    
void dfs(int i, int p)
{
    num[i] = low[i] = ++c;
    s.push(i);
    for (int ele:graph[i])
    {
        if (i==root) sub++;
        if (ele == p) continue;
        if (!num[ele]) 
        {
            dfs(ele, i);
            if (low[ele]>=num[i]) art[i] = 1;
            if (low[ele]==num[i])
            {
                while(s.top() != i)
                {
                    comp[s.top()] = d;
                    compsize[d]++;
                    s.pop();
                }
                comp[i] = d;
                compsize[d]++;
                s.pop();
                d++;
            }
        }
        low[i] = min(low[i], low[ele]);
    }
    if (num[i]==low[i] && comp[i]==-1)
    {
        art[i] = 1;
        while (s.top() != i)
        {
            comp[s.top()] = d;
            compsize[d]++;
            s.pop();
        }
        comp[i] = d;
        compsize[d]++;
        s.pop();
        d++;
    }
}
    
int dfs2(int i)
{
    vis[i] = 1;
    ll ss = 0;
    vector<int> cs;
    for (int ele:cgraph[i])
    {
        if (!vis[ele]) 
        {
            int h = dfs2(ele);
            sol -= compsize[i]*(h-compsize[ele])*(h-compsize[ele]-1);
            sol -= compsize[i]*compsize[ele]*(h-compsize[ele])*2;
            cs.push_back(ele);
            ss+=h;
        }
    }
    for (int ele:cs)
    {
        sol -= compsize[ele]*(sub-ss-compsize[i])*(sub-ss-compsize[i]-1);
        sol -= compsize[ele]*compsize[i]*(sub-ss-compsize[i])*2;
    }
    return ss+compsize[i];
}
    
int32_t main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    
    cin >> n >> m;
    graph.assign(n, vector<int>());
    cgraph.assign(5*n+m, vector<int>());
    compsize.assign(5*n+m, 0);
    low.assign(n, 0);
    num.assign(n, 0);
    comp.assign(n, -1);
    art.assign(n, 0);
    vis.assign(5*n+m, 0);
    subtree.assign(5*n+m, 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]) 
        {
            sub = 0;
            root = i;
            c = 0;
            dfs(i, -1);
            subtree[comp[i]] = c;
            sol += max((ll)0, c*(c-1)*(c-2));
            if (sub==1) art[i] = 0;
        }
    }
    
    for (int i = 0; i <n; i++)
    {
        if (art[i])
        {
            compsize[comp[i]]--;
            subtree[d] = subtree[comp[i]];
            comp[i] = d;
            compsize[d] = 1;
            d++;
        }
    }
    for (int i = 0; i <n; i++)
    {
        if (art[i])
        {
            for (int ele:graph[i])
            {
                if (art[ele] && ele > i) 
                {
                    cgraph[comp[i]].push_back(d);
                    cgraph[d].push_back(comp[i]);
                    cgraph[d].push_back(comp[ele]);
                    cgraph[comp[ele]].push_back(d);
                    d++;
                    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]])
        {
            sub = subtree[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 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 0 ms 348 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 94 ms 45652 KB Output is correct
2 Correct 80 ms 45904 KB Output is correct
3 Correct 104 ms 50512 KB Output is correct
4 Correct 83 ms 45208 KB Output is correct
5 Correct 86 ms 45904 KB Output is correct
6 Correct 117 ms 49232 KB Output is correct
7 Correct 102 ms 46420 KB Output is correct
8 Correct 131 ms 47132 KB Output is correct
9 Correct 95 ms 44504 KB Output is correct
10 Correct 92 ms 44424 KB Output is correct
11 Correct 81 ms 39964 KB Output is correct
12 Correct 79 ms 39760 KB Output is correct
13 Correct 75 ms 39248 KB Output is correct
14 Correct 75 ms 38996 KB Output is correct
15 Correct 63 ms 37200 KB Output is correct
16 Correct 59 ms 37200 KB Output is correct
17 Correct 12 ms 29276 KB Output is correct
18 Correct 11 ms 29300 KB Output is correct
19 Correct 12 ms 29276 KB Output is correct
20 Correct 12 ms 29272 KB Output is correct
21 Correct 12 ms 29276 KB Output is correct
22 Correct 11 ms 29276 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 888 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 1 ms 776 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 856 KB Output is correct
18 Correct 1 ms 856 KB Output is correct
19 Correct 1 ms 860 KB Output is correct
20 Correct 1 ms 860 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 45916 KB Output is correct
2 Correct 124 ms 46160 KB Output is correct
3 Correct 120 ms 45904 KB Output is correct
4 Correct 126 ms 45936 KB Output is correct
5 Correct 121 ms 46140 KB Output is correct
6 Correct 143 ms 57648 KB Output is correct
7 Correct 151 ms 54096 KB Output is correct
8 Correct 146 ms 51796 KB Output is correct
9 Correct 136 ms 50000 KB Output is correct
10 Correct 121 ms 45908 KB Output is correct
11 Correct 155 ms 46028 KB Output is correct
12 Correct 122 ms 45904 KB Output is correct
13 Correct 122 ms 45956 KB Output is correct
14 Correct 112 ms 44328 KB Output is correct
15 Correct 101 ms 42836 KB Output is correct
16 Correct 62 ms 37800 KB Output is correct
17 Correct 105 ms 47460 KB Output is correct
18 Correct 103 ms 47464 KB Output is correct
19 Correct 97 ms 47020 KB Output is correct
20 Correct 97 ms 46652 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Incorrect 1 ms 860 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 45992 KB Output is correct
2 Correct 128 ms 46048 KB Output is correct
3 Incorrect 130 ms 45940 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 0 ms 348 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 0 ms 348 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 -