oj.uz

Submission #674214

# Submission time Handle Problem Language Result Execution time Memory
674214 2022-12-23T13:33:52 Z Jarif_Rahman Duathlon (APIO18_duathlon) C++17
23 / 100
 1000 ms 1048576 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

int n, m;
vector<vector<int>> graph;
vector<int> sz;
ll ans = 0;

int N = 0;
void dfs(int nd, int ss){
    N++;
    sz[nd] = 1;
    for(int x: graph[nd]) if(x != ss) dfs(x, nd), sz[nd]+=sz[x];
}
void dfs2(int nd, int ss){
    for(int x: graph[nd]) if(x != ss) dfs2(x, nd);

    ans+=ll(N-sz[nd])*ll(sz[nd]-1);
    for(int x: graph[nd]) if(x != ss) ans+=ll(N-sz[x]-1)*ll(sz[x]);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    graph.resize(n);
    sz.resize(n, 0);

    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b; a--, b--;
        graph[a].pb(b);
        graph[b].pb(a);
    }

    for(int i = 0; i < n; i++) if(!sz[i]){
        N = 0;
        dfs(i, -1);
        dfs2(i, -1);
    }

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 683 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 683 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 1105 ms 558236 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 6228 KB Output is correct
2 Correct 42 ms 7428 KB Output is correct
3 Correct 44 ms 7472 KB Output is correct
4 Correct 52 ms 7448 KB Output is correct
5 Correct 44 ms 7428 KB Output is correct
6 Correct 55 ms 10844 KB Output is correct
7 Correct 58 ms 9676 KB Output is correct
8 Correct 46 ms 9036 KB Output is correct
9 Correct 85 ms 8692 KB Output is correct
10 Correct 59 ms 7532 KB Output is correct
11 Correct 48 ms 7480 KB Output is correct
12 Correct 56 ms 7480 KB Output is correct
13 Correct 44 ms 7632 KB Output is correct
14 Correct 35 ms 7212 KB Output is correct
15 Correct 37 ms 6988 KB Output is correct
16 Correct 20 ms 5984 KB Output is correct
17 Correct 27 ms 7720 KB Output is correct
18 Correct 31 ms 7756 KB Output is correct
19 Correct 39 ms 7796 KB Output is correct
20 Correct 56 ms 7816 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Runtime error 618 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 45 ms 6220 KB Output is correct
2 Correct 78 ms 7444 KB Output is correct
3 Runtime error 777 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 683 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 683 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -