oj.uz

Submission #85995

# Submission time Handle Problem Language Result Execution time Memory
85995 2018-11-23T17:17:17 Z fedoseevtimofey Duathlon (APIO18_duathlon) C++14
23 / 100
 101 ms 33240 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 1e5 + 7;

vector <int> g[N];
int cnt[N];
bool used[N];
int sz[N];
int cmp[N];
int par[N];

int x = 0;

void dfs(int u, int p = -1) {
    par[u] = p;
    used[u] = 1;
    cmp[u] = x;
    ++sz[x];
    cnt[u] = 1;
    for (auto v : g[u]) {
        if (!used[v]) {
            dfs(v, u);
            cnt[u] += cnt[v];
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            ++x;
            dfs(i);
        }
    }
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        vector <int> curs;
        int have = 0;
        for (auto j : g[i]) {
            if (j == par[i]) continue;
            curs.push_back(cnt[j]);
            have += cnt[j];
        }
        curs.push_back(sz[cmp[i]] - have - 1);
        have = sz[cmp[i]] - 1;
        for (auto i : curs) {
            ans += (ll)i * (have - i);
        }
    }
    cout << ans << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 11772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 11772 KB Output is correct
2 Correct 72 ms 11772 KB Output is correct
3 Correct 76 ms 11772 KB Output is correct
4 Correct 73 ms 11772 KB Output is correct
5 Correct 65 ms 12892 KB Output is correct
6 Correct 96 ms 16504 KB Output is correct
7 Correct 92 ms 16988 KB Output is correct
8 Correct 68 ms 17732 KB Output is correct
9 Correct 65 ms 18588 KB Output is correct
10 Correct 68 ms 19068 KB Output is correct
11 Correct 78 ms 20320 KB Output is correct
12 Correct 69 ms 21568 KB Output is correct
13 Correct 82 ms 22836 KB Output is correct
14 Correct 83 ms 24016 KB Output is correct
15 Correct 79 ms 24952 KB Output is correct
16 Correct 38 ms 25012 KB Output is correct
17 Correct 56 ms 27984 KB Output is correct
18 Correct 52 ms 28928 KB Output is correct
19 Correct 52 ms 30116 KB Output is correct
20 Correct 51 ms 31172 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31172 KB Output is correct
2 Correct 4 ms 31172 KB Output is correct
3 Incorrect 4 ms 31172 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 31172 KB Output is correct
2 Correct 101 ms 31896 KB Output is correct
3 Incorrect 96 ms 33240 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -