oj.uz

Submission #742124

# Submission time Handle Problem Language Result Execution time Memory
742124 2023-05-15T16:12:27 Z speedyArda Duathlon (APIO18_duathlon) C++14
8 / 100
 448 ms 1048576 KB 
#include "bits/stdc++.h"

using namespace std;
const int MAXN = 1e5+5;
vector< vector<int> > adj(MAXN);
bool visited[MAXN];
long long sz[MAXN];
long long add[MAXN];
int n, m;
pair<long long, bool> subtask3(int v, int p)
{
    pair<long long, bool> ans = {1, false};
    visited[v] = true;

    for(int e : adj[v])
    {
        if(e == p)
            continue;
        if(visited[e]) {
            ans.second = true;
            continue;
        }
        pair<long long, bool> temp = subtask3(e, v);
        ans.first += temp.first;
        ans.second |= temp.second;
    }
    return ans;
}

long long subtask5(int v, int p)
{
    long long ans = 0;
    visited[v] = true;
    sz[v] = 1;
    long long chi_size = 0;
    for(int e : adj[v])
    {
        if(e == p)
            continue;
        ans += subtask5(e, v);
        sz[v] += sz[e];
        chi_size += sz[e];
    }
    long long par_size = n - chi_size - 1;
    ans += par_size * chi_size;
    for(int e : adj[v])
    {
        ans += sz[e] * (n - sz[e] - 1);
    }
    return ans;
}
int main() 
{
    long long temp = 0;
    add[0] = 0;
    for(long long i = 1; i < MAXN; i++)
    {
        temp += i;
        add[i] = add[i - 1] + temp;
    }
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int f, s;
        cin >> f >> s;
        adj[f].push_back(s);
        adj[s].push_back(f);
    }

    int max_size = 0;
    for(int i = 1; i <= n; i++)
    {
        max_size = max(max_size, (int)adj[i].size());
    }
    long long ans = 0;
    if(max_size <= 2) // Subtask 3
    {
        for(int i = 1; i <= n; i++)
        {
            if(visited[i])
                continue;
            pair<long long, bool> curr = subtask3(i, -1);
            if(curr.second)
            {
                ans += curr.first * (curr.first - 1) * (curr.first - 2);
            } else if(curr.first >= 3)
            {
                ans += add[curr.first - 2] * 2LL;
            }
        }   
    } else 
    {
        for(int i = 1; i <= n; i++)
        {
            if(visited[i])
                continue;
            ans += subtask5(i, -1);
        }
    }


    cout << ans << "\n";
    
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 448 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 448 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 14668 KB Output is correct
2 Correct 93 ms 15608 KB Output is correct
3 Correct 92 ms 11784 KB Output is correct
4 Correct 89 ms 13648 KB Output is correct
5 Correct 88 ms 10444 KB Output is correct
6 Correct 99 ms 10388 KB Output is correct
7 Correct 98 ms 9384 KB Output is correct
8 Correct 90 ms 10056 KB Output is correct
9 Correct 88 ms 8660 KB Output is correct
10 Correct 92 ms 9300 KB Output is correct
11 Correct 71 ms 7652 KB Output is correct
12 Correct 73 ms 7604 KB Output is correct
13 Correct 61 ms 7356 KB Output is correct
14 Correct 60 ms 7252 KB Output is correct
15 Correct 44 ms 6664 KB Output is correct
16 Correct 48 ms 6676 KB Output is correct
17 Correct 3 ms 3448 KB Output is correct
18 Correct 3 ms 3444 KB Output is correct
19 Correct 3 ms 3540 KB Output is correct
20 Correct 3 ms 3448 KB Output is correct
21 Correct 3 ms 3540 KB Output is correct
22 Correct 3 ms 3456 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 7800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 7788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 448 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 448 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -