oj.uz

Submission #356374

# Submission time Handle Problem Language Result Execution time Memory
356374 2021-01-23T10:16:42 Z valerikk Duathlon (APIO18_duathlon) C++14
23 / 100
 272 ms 33644 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 3e5 + 7;
 
int n, m;
vector<pair<int, int>> g[N];
vector<int> gr[N];
int dep[N], low[N];
bool vis[N];
int col[N], cnt;
int sz[N];
long long ans;
int S;
 
void dfs(int v, int p = -1) {
    low[v] = dep[v];
    vis[v] = true;
    for (auto [u, i] : g[v]) {
        if (!vis[u]) {
            dep[u] = dep[v] + 1;
            dfs(u, i);
            low[v] = min(low[v], low[u]);
        } else {
            if (i != p)
                low[v] = min(low[v], dep[u]);
        }
    }
}
 
void paint(int v, int p = -1) {
    vis[v] = true;
    for (auto [u, i] : g[v]) {
        if (!vis[u]) {
            if (dep[v] <= low[u]) {
                col[i] = ++cnt;
            } else {
                col[i] = col[p];
            }
            paint(u, i);
        } else {
            if (i != p) {
                if (dep[u] < dep[v]) col[i] = col[p];
            }
        }
    }
}
 
int get_size(int v, int p = -1) {
    sz[v] = v <= n;
    for (int u : gr[v]) {
        if (u != p) {
            sz[v] += get_size(u, v);
        }
    }
    return sz[v];
}
 
void find_ans(int v, int p = -1) {
    vis[v] = true;
    for (int u : gr[v]) {
        if (u != p)
            find_ans(u, v);
    }
    if (v <= n) {
        int sum = 0;
        for (int u : gr[v]) {
            int sz_u = u == p ? S - sz[v] : sz[u];
            ans += (long long)sum * sz_u * 2;
            sum += sz_u;
        }
    }
}
 
int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            dep[i] = 0;
            dfs(i);
        }
    }
    for (int i = 1; i <= n; ++i)
        vis[i] = false;
    cnt = n;
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            paint(i);
        }
    }/*
    for (int i = 1; i <= m; ++i)
        cout << col[i] << " ";
    cout << endl;
    return 0;*/
    for (int i = 1; i <= n; ++i) {
        vector<int> v;
        for (auto [u, i] : g[i])
            v.push_back(col[i]);
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        for (int c : v) {
            // cout << min(i, c) << " " << max(i, c) << endl;
            gr[i].push_back(c);
            gr[c].push_back(i);
        }
    }
    for (int i = 1; i <= cnt; ++i)
        vis[i] = false;
    ans = 0;
    for (int i = 1; i <= cnt; ++i) {
        if (!vis[i]) {
            S = get_size(i);
            find_ans(i);
        }
    }
    cout << ans << endl;
    return 0;
}

Compilation message

count_triplets.cpp: In function 'void dfs(int, int)':
count_triplets.cpp:20:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |     for (auto [u, i] : g[v]) {
      |               ^
count_triplets.cpp: In function 'void paint(int, int)':
count_triplets.cpp:34:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |     for (auto [u, i] : g[v]) {
      |               ^
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:109:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  109 |         for (auto [u, i] : g[i])
      |                   ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 172 ms 31380 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 11 ms 14572 KB Output is correct
2 Correct 11 ms 14592 KB Output is correct
3 Correct 11 ms 14572 KB Output is correct
4 Correct 11 ms 14700 KB Output is correct
5 Correct 11 ms 14724 KB Output is correct
6 Correct 11 ms 14572 KB Output is correct
7 Correct 11 ms 14700 KB Output is correct
8 Correct 12 ms 14572 KB Output is correct
9 Correct 13 ms 14580 KB Output is correct
10 Correct 11 ms 14572 KB Output is correct
11 Correct 13 ms 14572 KB Output is correct
12 Correct 11 ms 14572 KB Output is correct
13 Correct 11 ms 14572 KB Output is correct
14 Correct 11 ms 14572 KB Output is correct
15 Correct 11 ms 14572 KB Output is correct
16 Correct 12 ms 14572 KB Output is correct
17 Correct 11 ms 14572 KB Output is correct
18 Correct 11 ms 14572 KB Output is correct
19 Correct 12 ms 14572 KB Output is correct
20 Correct 11 ms 14572 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 27392 KB Output is correct
2 Correct 225 ms 27628 KB Output is correct
3 Correct 206 ms 27500 KB Output is correct
4 Correct 218 ms 27500 KB Output is correct
5 Correct 189 ms 27500 KB Output is correct
6 Correct 251 ms 33644 KB Output is correct
7 Correct 223 ms 31724 KB Output is correct
8 Correct 228 ms 30700 KB Output is correct
9 Correct 243 ms 29420 KB Output is correct
10 Correct 184 ms 27500 KB Output is correct
11 Correct 195 ms 27500 KB Output is correct
12 Correct 216 ms 27500 KB Output is correct
13 Correct 244 ms 27376 KB Output is correct
14 Correct 193 ms 26860 KB Output is correct
15 Correct 139 ms 25964 KB Output is correct
16 Correct 103 ms 23148 KB Output is correct
17 Correct 141 ms 28000 KB Output is correct
18 Correct 166 ms 27996 KB Output is correct
19 Correct 159 ms 27988 KB Output is correct
20 Correct 149 ms 27996 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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