oj.uz

Submission #926210

# Submission time Handle Problem Language Result Execution time Memory
926210 2024-02-12T17:21:57 Z codefox Duathlon (APIO18_duathlon) C++14
31 / 100
 123 ms 29108 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);
    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]++;
                    s.pop();
                }
                comp[ele] = d;
                compsize[d]++;
                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]++;
            s.pop();
        }
        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 (int ele:cgraph[i])
    {
        if (vis[ele]) continue;
        dfs2(ele);
        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));

    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(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 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 Correct 1 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 1 ms 348 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 0 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 348 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 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 Correct 1 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 1 ms 348 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 0 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 348 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 87 ms 26968 KB Output is correct
2 Correct 85 ms 27080 KB Output is correct
3 Correct 82 ms 25588 KB Output is correct
4 Correct 77 ms 24912 KB Output is correct
5 Correct 79 ms 23124 KB Output is correct
6 Correct 82 ms 24712 KB Output is correct
7 Correct 91 ms 23124 KB Output is correct
8 Correct 83 ms 23316 KB Output is correct
9 Correct 80 ms 21584 KB Output is correct
10 Correct 78 ms 21820 KB Output is correct
11 Correct 66 ms 19852 KB Output is correct
12 Correct 83 ms 19792 KB Output is correct
13 Correct 75 ms 20052 KB Output is correct
14 Correct 60 ms 19792 KB Output is correct
15 Correct 53 ms 19672 KB Output is correct
16 Correct 63 ms 19448 KB Output is correct
17 Correct 11 ms 15196 KB Output is correct
18 Correct 11 ms 15192 KB Output is correct
19 Correct 10 ms 15172 KB Output is correct
20 Correct 11 ms 15196 KB Output is correct
21 Correct 11 ms 15120 KB Output is correct
22 Correct 11 ms 15196 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 2 ms 604 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 600 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 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 604 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 98 ms 22796 KB Output is correct
2 Correct 101 ms 22636 KB Output is correct
3 Correct 100 ms 22612 KB Output is correct
4 Correct 123 ms 22640 KB Output is correct
5 Correct 91 ms 22612 KB Output is correct
6 Correct 118 ms 29108 KB Output is correct
7 Correct 103 ms 27684 KB Output is correct
8 Correct 121 ms 26428 KB Output is correct
9 Correct 104 ms 25124 KB Output is correct
10 Correct 101 ms 22612 KB Output is correct
11 Correct 107 ms 22608 KB Output is correct
12 Correct 101 ms 22656 KB Output is correct
13 Correct 115 ms 22548 KB Output is correct
14 Correct 103 ms 22128 KB Output is correct
15 Correct 84 ms 21832 KB Output is correct
16 Correct 56 ms 20144 KB Output is correct
17 Correct 88 ms 25120 KB Output is correct
18 Correct 81 ms 25388 KB Output is correct
19 Correct 110 ms 25020 KB Output is correct
20 Correct 82 ms 24540 KB Output is correct

Subtask #6
0 / 15.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 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 110 ms 22612 KB Output is correct
2 Correct 113 ms 22388 KB Output is correct
3 Incorrect 94 ms 22228 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 Correct 1 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 1 ms 348 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 0 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 348 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 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 Correct 1 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 1 ms 348 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 0 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Incorrect 0 ms 348 KB Output isn't correct
23 Halted 0 ms 0 KB -