oj.uz

Submission #924350

# Submission time Handle Problem Language Result Execution time Memory
924350 2024-02-08T21:27:55 Z codefox Duathlon (APIO18_duathlon) C++14
31 / 100
 173 ms 52984 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, vector<int>());
    compsize.assign(5*n, 0);
    low.assign(n, 0);
    num.assign(n, 0);
    comp.assign(n, -1);
    art.assign(n, 0);
    vis.assign(5*n, 0);
    subtree.assign(5*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);
    }
    
    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 344 KB Output is correct
2 Correct 0 ms 344 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 344 KB Output is correct
2 Correct 0 ms 344 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 68 ms 41044 KB Output is correct
2 Correct 75 ms 41040 KB Output is correct
3 Correct 100 ms 45700 KB Output is correct
4 Correct 79 ms 40532 KB Output is correct
5 Correct 97 ms 41008 KB Output is correct
6 Correct 99 ms 44556 KB Output is correct
7 Correct 97 ms 41808 KB Output is correct
8 Correct 108 ms 42532 KB Output is correct
9 Correct 119 ms 39792 KB Output is correct
10 Correct 96 ms 39764 KB Output is correct
11 Correct 81 ms 36432 KB Output is correct
12 Correct 99 ms 36564 KB Output is correct
13 Correct 76 ms 36180 KB Output is correct
14 Correct 75 ms 35924 KB Output is correct
15 Correct 62 ms 35332 KB Output is correct
16 Correct 60 ms 35156 KB Output is correct
17 Correct 12 ms 29436 KB Output is correct
18 Correct 12 ms 29272 KB Output is correct
19 Correct 12 ms 29272 KB Output is correct
20 Correct 13 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 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 856 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 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 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 600 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 856 KB Output is correct
17 Correct 1 ms 860 KB Output is correct
18 Correct 1 ms 604 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 123 ms 41380 KB Output is correct
2 Correct 125 ms 41296 KB Output is correct
3 Correct 121 ms 41296 KB Output is correct
4 Correct 121 ms 41300 KB Output is correct
5 Correct 141 ms 41288 KB Output is correct
6 Correct 142 ms 52984 KB Output is correct
7 Correct 164 ms 49232 KB Output is correct
8 Correct 154 ms 47260 KB Output is correct
9 Correct 155 ms 45068 KB Output is correct
10 Correct 125 ms 41300 KB Output is correct
11 Correct 142 ms 41296 KB Output is correct
12 Correct 123 ms 41296 KB Output is correct
13 Correct 126 ms 41308 KB Output is correct
14 Correct 111 ms 40276 KB Output is correct
15 Correct 99 ms 39424 KB Output is correct
16 Correct 71 ms 36128 KB Output is correct
17 Correct 90 ms 42944 KB Output is correct
18 Correct 104 ms 42292 KB Output is correct
19 Correct 91 ms 42160 KB Output is correct
20 Correct 96 ms 41744 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 123 ms 41276 KB Output is correct
2 Correct 173 ms 41216 KB Output is correct
3 Incorrect 143 ms 40348 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 344 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 344 KB Output is correct
2 Correct 0 ms 344 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 -