oj.uz

Submission #742126

# Submission time Handle Problem Language Result Execution time Memory
742126 2023-05-15T16:24:47 Z speedyArda Duathlon (APIO18_duathlon) C++14
8 / 100
 697 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])
    {
        if(e == p)
            continue;
        ans += sz[e] * ((long long)n - sz[e] - 1LL);
    }
    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 459 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 459 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 91 ms 14488 KB Output is correct
2 Correct 105 ms 14408 KB Output is correct
3 Correct 84 ms 10436 KB Output is correct
4 Correct 83 ms 12476 KB Output is correct
5 Correct 104 ms 9260 KB Output is correct
6 Correct 102 ms 9152 KB Output is correct
7 Correct 113 ms 8324 KB Output is correct
8 Correct 100 ms 8816 KB Output is correct
9 Correct 100 ms 7420 KB Output is correct
10 Correct 101 ms 8148 KB Output is correct
11 Correct 84 ms 6560 KB Output is correct
12 Correct 85 ms 6452 KB Output is correct
13 Correct 71 ms 6508 KB Output is correct
14 Correct 61 ms 6276 KB Output is correct
15 Correct 67 ms 6080 KB Output is correct
16 Correct 49 ms 5964 KB Output is correct
17 Correct 5 ms 3540 KB Output is correct
18 Correct 3 ms 3540 KB Output is correct
19 Correct 3 ms 3540 KB Output is correct
20 Correct 3 ms 3540 KB Output is correct
21 Correct 3 ms 3540 KB Output is correct
22 Correct 3 ms 3540 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3412 KB Output is correct
2 Correct 3 ms 3432 KB Output is correct
3 Correct 3 ms 3412 KB Output is correct
4 Correct 3 ms 3452 KB Output is correct
5 Correct 3 ms 3412 KB Output is correct
6 Correct 3 ms 3412 KB Output is correct
7 Correct 3 ms 3420 KB Output is correct
8 Correct 3 ms 3412 KB Output is correct
9 Correct 3 ms 3412 KB Output is correct
10 Incorrect 3 ms 3412 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 7512 KB Output is correct
2 Correct 85 ms 8696 KB Output is correct
3 Correct 108 ms 8712 KB Output is correct
4 Correct 102 ms 8896 KB Output is correct
5 Correct 82 ms 8780 KB Output is correct
6 Correct 84 ms 12140 KB Output is correct
7 Correct 108 ms 12024 KB Output is correct
8 Correct 109 ms 11172 KB Output is correct
9 Correct 114 ms 10488 KB Output is correct
10 Incorrect 100 ms 8780 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3412 KB Output is correct
2 Correct 4 ms 3456 KB Output is correct
3 Runtime error 611 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 7504 KB Output is correct
2 Correct 77 ms 8752 KB Output is correct
3 Runtime error 697 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 459 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 459 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -