oj.uz

Submission #260909

# Submission time Handle Problem Language Result Execution time Memory
260909 2020-08-11T07:34:13 Z SorahISA Duathlon (APIO18_duathlon) C++17
23 / 100
 1000 ms 1048580 KB 
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double
using pii = pair<int, int>;
template<typename T>
using prior = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using Prior = priority_queue<T>;

#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back
#define fastIO() ios_base::sync_with_stdio(false), cin.tie(0)

const int maxn = 1E5 + 5;

int ans = 0;
vector<int> adj[maxn], vis(maxn), sz(maxn, 1);

void dfs(int now, int lst) {
    vis[now] = 1;
    for (auto x : adj[now]) {
        if (x != lst) dfs(x, now), sz[now] += sz[x];
    }
}

void dfs2(int now, int lst, int rt) {
    for (auto x : adj[now]) {
        if (x == lst) continue;
        ans += sz[x] * (sz[now] - sz[x] - 1);
        dfs2(x, now, rt);
    }
    ans += 2 * (sz[now] - 1) * (sz[rt] - sz[now]);
}

int32_t main() {
    fastIO();
    
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].eb(v), adj[v].eb(u);
    }
    
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            dfs(i, -1), dfs2(i, -1, i);
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 7928 KB Output is correct
2 Correct 85 ms 8312 KB Output is correct
3 Correct 65 ms 8184 KB Output is correct
4 Correct 65 ms 8184 KB Output is correct
5 Correct 76 ms 8184 KB Output is correct
6 Correct 106 ms 9824 KB Output is correct
7 Correct 86 ms 9592 KB Output is correct
8 Correct 74 ms 9208 KB Output is correct
9 Correct 73 ms 8952 KB Output is correct
10 Correct 63 ms 8184 KB Output is correct
11 Correct 62 ms 8184 KB Output is correct
12 Correct 62 ms 8184 KB Output is correct
13 Correct 62 ms 8184 KB Output is correct
14 Correct 53 ms 7928 KB Output is correct
15 Correct 47 ms 7800 KB Output is correct
16 Correct 31 ms 6912 KB Output is correct
17 Correct 42 ms 8300 KB Output is correct
18 Correct 43 ms 8424 KB Output is correct
19 Correct 47 ms 8672 KB Output is correct
20 Correct 48 ms 8408 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4352 KB Output is correct
2 Correct 4 ms 4384 KB Output is correct
3 Runtime error 806 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 8056 KB Output is correct
2 Correct 81 ms 8132 KB Output is correct
3 Runtime error 976 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 603 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 603 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -