oj.uz

Submission #742811

# Submission time Handle Problem Language Result Execution time Memory
742811 2023-05-17T02:43:23 Z PixelCat Duathlon (APIO18_duathlon) C++14
23 / 100
 58 ms 22800 KB 
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 100010;

vector<int> adj[MAXN];
int siz[MAXN];

void dfs_siz(int n, int p) {
    siz[n] = 1;
    for(auto &i:adj[n]) if(i != p) {
        assert(!siz[i]);
        dfs_siz(i, n);
        siz[n] += siz[i];
    }
}

int ans;
#define C(x) ((x) * ((x) - 1))
void dfs_ans(int n, int p, int tot_n) {
    ans += C(tot_n - 1);
    for(auto &i:adj[n]) {
        int s = siz[i];
        if(i == p) s = tot_n - siz[n];
        ans -= C(s);

        if(i != p) dfs_ans(i, n, tot_n);
    }
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // =^-w-^= nya
    int n, m; cin >> n >> m;
    while(m--) {
        int a, b; cin >> a >> b;
        adj[a].eb(b);
        adj[b].eb(a);
    }
    ans = 0;
    For(i, 1, n) if(!siz[i]) {
        dfs_siz(i, i);
        dfs_ans(i, i, siz[i]);
    }
    cout << ans << "\n";
    return 0;
}

/*

4 3
1 2
2 3
3 4

4 4
1 2
2 3
3 4
4 2

*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 5240 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 5240 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 22800 KB Execution killed with signal 6
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 3 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 2692 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2684 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2692 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 2684 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2692 KB Output is correct
18 Correct 3 ms 2640 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 50 ms 7248 KB Output is correct
2 Correct 47 ms 7304 KB Output is correct
3 Correct 51 ms 7244 KB Output is correct
4 Correct 49 ms 7224 KB Output is correct
5 Correct 40 ms 7280 KB Output is correct
6 Correct 54 ms 10076 KB Output is correct
7 Correct 58 ms 9420 KB Output is correct
8 Correct 58 ms 8836 KB Output is correct
9 Correct 50 ms 8216 KB Output is correct
10 Correct 39 ms 7276 KB Output is correct
11 Correct 39 ms 7304 KB Output is correct
12 Correct 39 ms 7268 KB Output is correct
13 Correct 44 ms 7216 KB Output is correct
14 Correct 40 ms 7056 KB Output is correct
15 Correct 30 ms 6868 KB Output is correct
16 Correct 21 ms 5972 KB Output is correct
17 Correct 31 ms 7408 KB Output is correct
18 Correct 28 ms 7404 KB Output is correct
19 Correct 28 ms 7452 KB Output is correct
20 Correct 31 ms 7504 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2684 KB Output is correct
3 Runtime error 4 ms 5332 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7200 KB Output is correct
2 Correct 44 ms 7116 KB Output is correct
3 Runtime error 44 ms 13560 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 5240 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 5240 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -