oj.uz

Submission #369832

# Submission time Handle Problem Language Result Execution time Memory
369832 2021-02-22T14:46:29 Z abc864197532 Duathlon (APIO18_duathlon) C++17
31 / 100
 196 ms 38916 KB 
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}
const int mod = 1e9 + 7, abc = 864197532, N = 100087, logN = 17, K = 333;

vector <int> adj[N], bcc[N];
int low[N], dep[N], nbcc = 0;
bool vis[N], cut[N];
stack <int> stk;

void dfs(int v, int pa) {
    vis[v] = true;
    low[v] = dep[v] = ~pa ? dep[pa] + 1 : 0;
    stk.push(v);
    int ch = 0;
    for (int u : adj[v]) if (u != pa) {
        if (vis[u]) low[v] = min(low[v], dep[u]);
        else {
            dfs(u, v);
            low[v] = min(low[v], low[u]);
            ch++;
            if (low[u] >= dep[v]) {
                cut[v] = true;
                int x;
                do {
                    x = stk.top(); stk.pop();
                    bcc[x].pb(nbcc);
                } while (x != u);
                bcc[v].pb(nbcc++);
            }
        }
    }
    if (pa == -1 && ch < 2) cut[v] = false;
}

vector <int> newadj[N * 2];
bool vis2[N * 2];
int sz[N * 2], p[N * 2], val[N * 2];
vector <int> cc;

lli C2(int n) {
    return 1ll * n * (n - 1);
}

void dfs2(int v, int pa) {
    sz[v] = val[v];
    vis2[v] = true;
    p[v] = pa;
    cc.pb(v);
    for (int u : newadj[v]) if (u != pa) {
        dfs2(u, v);
        sz[v] += sz[u];
    }
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0, u, v; i < m; ++i) {
        cin >> u >> v, --u, --v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for (int i = 0; i < n; ++i) if (!vis[i]) dfs(i, -1);
    for (int i = 0; i < n; ++i) if (cut[i]) {
        for (int j : bcc[i]) {
            newadj[i].pb(j + N);
            newadj[j + N].pb(i);
        }
    }
    for (int i = 0; i < n; ++i) if (bcc[i].size() == 1) {
        val[bcc[i][0] + N]++;
    }
    for (int i = 0; i < n; ++i) if (cut[i]) val[i]++;
    lli ans = 0;
    for (int i = N; i < nbcc + N; ++i) if (!vis2[i]) {
        dfs2(i, -1);
        int m = sz[i];
        if (m <= 2) continue;
        ans += C2(m - 1) * m;
        for (int j : cc) {
            if (j < n) {
                for (int k : newadj[j]) {
                    if (k == p[j]) ans -= C2(m - sz[j] - val[k]) * val[j];
                    else ans -= C2(sz[k] - val[k]) * val[j];
                }
            } else {
                for (int k : newadj[j]) {
                    if (k == p[j]) ans -= C2(m - sz[j]) * val[j];
                    else ans -= C2(sz[k]) * val[j];
                }
            }
        }
        cc.clear();
    }
    cout << ans << endl;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 29420 KB Output is correct
2 Correct 110 ms 29548 KB Output is correct
3 Correct 136 ms 28808 KB Output is correct
4 Correct 109 ms 29928 KB Output is correct
5 Correct 116 ms 25452 KB Output is correct
6 Correct 142 ms 29804 KB Output is correct
7 Correct 138 ms 25452 KB Output is correct
8 Correct 144 ms 27628 KB Output is correct
9 Correct 142 ms 24044 KB Output is correct
10 Correct 128 ms 24560 KB Output is correct
11 Correct 94 ms 20832 KB Output is correct
12 Correct 94 ms 20716 KB Output is correct
13 Correct 82 ms 20204 KB Output is correct
14 Correct 82 ms 20076 KB Output is correct
15 Correct 59 ms 18668 KB Output is correct
16 Correct 63 ms 18540 KB Output is correct
17 Correct 9 ms 11244 KB Output is correct
18 Correct 9 ms 11244 KB Output is correct
19 Correct 9 ms 11116 KB Output is correct
20 Correct 9 ms 11116 KB Output is correct
21 Correct 9 ms 11244 KB Output is correct
22 Correct 10 ms 11116 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 25700 KB Output is correct
2 Correct 156 ms 25776 KB Output is correct
3 Correct 152 ms 25572 KB Output is correct
4 Correct 161 ms 25684 KB Output is correct
5 Correct 159 ms 25700 KB Output is correct
6 Correct 196 ms 38916 KB Output is correct
7 Correct 176 ms 30572 KB Output is correct
8 Correct 170 ms 29292 KB Output is correct
9 Correct 163 ms 28132 KB Output is correct
10 Correct 146 ms 25060 KB Output is correct
11 Correct 145 ms 25700 KB Output is correct
12 Correct 144 ms 24852 KB Output is correct
13 Correct 139 ms 24940 KB Output is correct
14 Correct 127 ms 23916 KB Output is correct
15 Correct 108 ms 22892 KB Output is correct
16 Correct 66 ms 19308 KB Output is correct
17 Correct 84 ms 23148 KB Output is correct
18 Correct 75 ms 23136 KB Output is correct
19 Correct 74 ms 23196 KB Output is correct
20 Correct 73 ms 23140 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 25700 KB Output is correct
2 Correct 156 ms 25836 KB Output is correct
3 Incorrect 153 ms 24940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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