oj.uz

Submission #924352

# Submission time Handle Problem Language Result Execution time Memory
924352 2024-02-08T21:32:12 Z codefox Duathlon (APIO18_duathlon) C++14
31 / 100
 171 ms 57508 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 ele:comp)
    {
        if (!vis[ele])
        {
            sub = subtree[ele];
            dfs2(ele);
        }
    }
    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 72 ms 45656 KB Output is correct
2 Correct 75 ms 45836 KB Output is correct
3 Correct 99 ms 50436 KB Output is correct
4 Correct 86 ms 45136 KB Output is correct
5 Correct 100 ms 45756 KB Output is correct
6 Correct 135 ms 49124 KB Output is correct
7 Correct 111 ms 46416 KB Output is correct
8 Correct 111 ms 47188 KB Output is correct
9 Correct 111 ms 44572 KB Output is correct
10 Correct 93 ms 44372 KB Output is correct
11 Correct 79 ms 39936 KB Output is correct
12 Correct 79 ms 39764 KB Output is correct
13 Correct 98 ms 39236 KB Output is correct
14 Correct 75 ms 38992 KB Output is correct
15 Correct 58 ms 37172 KB Output is correct
16 Correct 58 ms 37200 KB Output is correct
17 Correct 15 ms 29272 KB Output is correct
18 Correct 12 ms 29276 KB Output is correct
19 Correct 12 ms 29276 KB Output is correct
20 Correct 13 ms 29432 KB Output is correct
21 Correct 12 ms 29528 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 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 676 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 860 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 860 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 2 ms 860 KB Output is correct
18 Correct 1 ms 860 KB Output is correct
19 Correct 1 ms 860 KB Output is correct
20 Correct 2 ms 856 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 46068 KB Output is correct
2 Correct 123 ms 45972 KB Output is correct
3 Correct 137 ms 45908 KB Output is correct
4 Correct 134 ms 46160 KB Output is correct
5 Correct 124 ms 46160 KB Output is correct
6 Correct 171 ms 57508 KB Output is correct
7 Correct 144 ms 54100 KB Output is correct
8 Correct 144 ms 51796 KB Output is correct
9 Correct 153 ms 50256 KB Output is correct
10 Correct 131 ms 46052 KB Output is correct
11 Correct 126 ms 46164 KB Output is correct
12 Correct 118 ms 45980 KB Output is correct
13 Correct 153 ms 46396 KB Output is correct
14 Correct 116 ms 44328 KB Output is correct
15 Correct 99 ms 42832 KB Output is correct
16 Correct 89 ms 37684 KB Output is correct
17 Correct 103 ms 47592 KB Output is correct
18 Correct 100 ms 47188 KB Output is correct
19 Correct 98 ms 47024 KB Output is correct
20 Correct 106 ms 46424 KB Output is correct

Subtask #6
0 / 15.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 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 142 ms 46168 KB Output is correct
2 Correct 133 ms 45908 KB Output is correct
3 Incorrect 127 ms 45908 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 -