oj.uz

Submission #698553

# Submission time Handle Problem Language Result Execution time Memory
698553 2023-02-13T18:49:05 Z Hanksburger Duathlon (APIO18_duathlon) C++17
23 / 100
 1000 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
long long sz[100005], cnt, ans;
vector<long long> adj[100005];
bool visited[100005];
void dfs1(long long u, long long p)
{
    cnt++;
    visited[u]=sz[u]=1;
    for (long long v:adj[u])
    {
        if (v==p)
            continue;
        dfs1(v, u);
        sz[u]+=sz[v];
    }
}
void dfs2(long long u, long long p)
{
    vector<long long> vec;
    vec.push_back(cnt-sz[u]);
    for (long long v:adj[u])
    {
        if (v==p)
            continue;
        dfs2(v, u);
        vec.push_back(sz[v]);
    }
    long long sum1=0, sum2=0;
    for (long long i=0; i<vec.size(); i++)
    {
        sum1+=vec[i];
        sum2+=vec[i]*vec[i];
    }
    ans+=sum1*sum1-sum2;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, m;
    cin >> n >> m;
    for (long long i=1; i<=m; i++)
    {
        long long u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (long long i=1; i<=n; i++)
    {
        if (!visited[i])
        {
            cnt=0;
            dfs1(i, 0);
            dfs2(i, 0);
        }
    }
    cout << ans;
}

Compilation message

count_triplets.cpp: In function 'void dfs1(long long int, long long int)':
count_triplets.cpp:9:21: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    9 |     visited[u]=sz[u]=1;
      |                ~~~~~^~
count_triplets.cpp: In function 'void dfs2(long long int, long long int)':
count_triplets.cpp:30:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (long long i=0; i<vec.size(); i++)
      |                         ~^~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1103 ms 515160 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2684 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2680 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2692 KB Output is correct
18 Correct 2 ms 2688 KB Output is correct
19 Correct 2 ms 2644 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 8460 KB Output is correct
2 Correct 56 ms 8500 KB Output is correct
3 Correct 51 ms 8440 KB Output is correct
4 Correct 65 ms 8448 KB Output is correct
5 Correct 51 ms 8420 KB Output is correct
6 Correct 82 ms 15592 KB Output is correct
7 Correct 67 ms 13360 KB Output is correct
8 Correct 62 ms 12160 KB Output is correct
9 Correct 62 ms 10964 KB Output is correct
10 Correct 51 ms 8528 KB Output is correct
11 Correct 50 ms 8524 KB Output is correct
12 Correct 49 ms 8452 KB Output is correct
13 Correct 52 ms 8612 KB Output is correct
14 Correct 43 ms 8140 KB Output is correct
15 Correct 38 ms 7832 KB Output is correct
16 Correct 24 ms 6508 KB Output is correct
17 Correct 30 ms 10172 KB Output is correct
18 Correct 36 ms 9836 KB Output is correct
19 Correct 36 ms 9844 KB Output is correct
20 Correct 34 ms 9428 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2692 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Runtime error 525 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 54 ms 8424 KB Output is correct
2 Correct 80 ms 8364 KB Output is correct
3 Runtime error 686 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 533 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 533 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -