oj.uz

Submission #369831

# Submission time Handle Problem Language Result Execution time Memory
369831 2021-02-22T14:41:36 Z abc864197532 Duathlon (APIO18_duathlon) C++17
31 / 100
 218 ms 39016 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]);
                    else ans -= C2(sz[k] - val[k]);
                }
            } 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 9856 KB Output is correct
3 Correct 6 ms 9836 KB Output is correct
4 Correct 6 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 9856 KB Output is correct
3 Correct 6 ms 9836 KB Output is correct
4 Correct 6 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 92 ms 29548 KB Output is correct
2 Correct 101 ms 29456 KB Output is correct
3 Correct 132 ms 28656 KB Output is correct
4 Correct 108 ms 29804 KB Output is correct
5 Correct 130 ms 25600 KB Output is correct
6 Correct 174 ms 29952 KB Output is correct
7 Correct 138 ms 25452 KB Output is correct
8 Correct 145 ms 27500 KB Output is correct
9 Correct 149 ms 24044 KB Output is correct
10 Correct 156 ms 24688 KB Output is correct
11 Correct 99 ms 20844 KB Output is correct
12 Correct 98 ms 20716 KB Output is correct
13 Correct 88 ms 20204 KB Output is correct
14 Correct 83 ms 20076 KB Output is correct
15 Correct 59 ms 18668 KB Output is correct
16 Correct 64 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 11264 KB Output is correct
21 Correct 8 ms 11244 KB Output is correct
22 Correct 9 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 8 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 8 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 8 ms 9964 KB Output is correct
14 Correct 7 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 8 ms 9984 KB Output is correct
19 Correct 8 ms 9964 KB Output is correct
20 Correct 6 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 25828 KB Output is correct
3 Correct 144 ms 25572 KB Output is correct
4 Correct 145 ms 25572 KB Output is correct
5 Correct 157 ms 25572 KB Output is correct
6 Correct 218 ms 39016 KB Output is correct
7 Correct 173 ms 30572 KB Output is correct
8 Correct 172 ms 29296 KB Output is correct
9 Correct 170 ms 28088 KB Output is correct
10 Correct 143 ms 25060 KB Output is correct
11 Correct 148 ms 25700 KB Output is correct
12 Correct 141 ms 24808 KB Output is correct
13 Correct 174 ms 24956 KB Output is correct
14 Correct 122 ms 23788 KB Output is correct
15 Correct 110 ms 22892 KB Output is correct
16 Correct 63 ms 19308 KB Output is correct
17 Correct 76 ms 23012 KB Output is correct
18 Correct 72 ms 23136 KB Output is correct
19 Correct 76 ms 23196 KB Output is correct
20 Correct 76 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 144 ms 25700 KB Output is correct
2 Correct 151 ms 25836 KB Output is correct
3 Incorrect 152 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 9856 KB Output is correct
3 Correct 6 ms 9836 KB Output is correct
4 Correct 6 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 9856 KB Output is correct
3 Correct 6 ms 9836 KB Output is correct
4 Correct 6 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 -