oj.uz

Submission #128358

# Submission time Handle Problem Language Result Execution time Memory
128358 2019-07-10T19:04:13 Z shafinalam Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 1048580 KB 
#include <bits/stdc++.h>

using namespace std;
const int mxn = 1e5+5;
typedef long long ll;
vector<int>adj[mxn];
ll sub[mxn];
bool vis[mxn];
ll ans = 0;

void dfs1(int u, int p)
{
    sub[u] = 1;
    vis[u] = 1;
    for(auto v : adj[u])
    {
        if(v==p) continue;
        dfs1(v, u);
        sub[u]+=sub[v];
    }
}
void dfs2(int u, int p, int root)
{
    ans+=((sub[root]-sub[u])*(sub[u]-1)*2);
    for(auto v : adj[u])
    {
        if(v==p) continue;
        dfs2(v, u, root);
        ans+=((sub[u]-sub[v]-1)*sub[v]);
    }
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);

    for(int i = 0; i < m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i = 1; i <= n; i++)
    {
        if(!vis[i])
        {
            dfs1(i, i);
            dfs2(i, i, i);
        }
    }
    printf("%lld\n", ans);
    return 0;
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
count_triplets.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1002 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1002 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 6776 KB Output is correct
2 Correct 95 ms 8056 KB Output is correct
3 Correct 94 ms 8056 KB Output is correct
4 Correct 96 ms 8032 KB Output is correct
5 Correct 102 ms 8088 KB Output is correct
6 Correct 139 ms 12252 KB Output is correct
7 Correct 139 ms 10752 KB Output is correct
8 Correct 136 ms 9976 KB Output is correct
9 Correct 144 ms 9464 KB Output is correct
10 Correct 97 ms 8056 KB Output is correct
11 Correct 93 ms 8056 KB Output is correct
12 Correct 93 ms 8200 KB Output is correct
13 Correct 93 ms 7984 KB Output is correct
14 Correct 90 ms 7800 KB Output is correct
15 Correct 73 ms 7544 KB Output is correct
16 Correct 47 ms 6564 KB Output is correct
17 Correct 60 ms 8304 KB Output is correct
18 Correct 62 ms 8376 KB Output is correct
19 Correct 63 ms 8300 KB Output is correct
20 Correct 57 ms 8312 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 5 ms 2724 KB Output is correct
3 Execution timed out 1134 ms 1037912 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 6820 KB Output is correct
2 Correct 109 ms 8088 KB Output is correct
3 Execution timed out 1141 ms 925636 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1002 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1002 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -