oj.uz

Submission #260931

# Submission time Handle Problem Language Result Execution time Memory
260931 2020-08-11T08:14:14 Z wiwiho Duathlon (APIO18_duathlon) C++14
31 / 100
 180 ms 33656 KB 
#include <bits/stdc++.h>

#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define printv(a, b) {bool pvs = false; \
for(auto i : a){ \
    if(pvs) b << ' '; \
    b << i; pvs = true; \
} \
b << '\n';}

using namespace std;

typedef long long ll;

const ll MAX = 2147483647;

vector<set<int>> g;
vector<ll> sz, cnt;

ll ans = 0;
void dfs(int now, int p){
    sz[now] = cnt[now];
    for(int i : g[now]){
        if(i == p) continue;
        dfs(i, now);
        sz[now] += sz[i];
    }
}

ll r = 0;
void dfs2(int now, int p){
    vector<ll> tmp;
    ll sum = 0;
    for(int i : g[now]){
        if(i == p) continue;
        dfs2(i, now);
        sum += sz[i];
        tmp.eb(sz[i]);
    }
    sum += r - sz[now];
    tmp.eb(r - sz[now]);
    //cerr << now << " " << cnt[now] << "\n";
    //printv(tmp, cerr);
    for(ll i : tmp){
        ans += (sum - i) * i * cnt[now];
        if(cnt[now] >= 3) ans += i * (cnt[now] - 1) * (cnt[now] - 2) * 2;
        if(cnt[now] >= 2) ans += i * (cnt[now] - 1) * 2;
    }
    ans += cnt[now] * (cnt[now] - 1) * (cnt[now] - 2);
}

vector<vector<int>> tg;
vector<int> bccid;
vector<int> ts, low;
int bcc = 1, tts = 0;
stack<int> st;

void dfst(int now, int p){
    low[now] = ts[now] = tts++;
    st.push(now);
    for(int i : tg[now]){
        if(i == p) continue;
        if(ts[i] != -1) low[now] = min(low[now], ts[i]);
        else{
            dfst(i, now);
            low[now] = min(low[now], low[i]);
        }
    }
    if(low[now] > ts[p] || now == p){
        int lst = -1;
        while(lst != now){
            bccid[st.top()] = bcc;
            lst = st.top();
            cnt[bcc]++;
            st.pop();
        }
        bcc++;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    g.resize(n + 1);
    sz.resize(n + 1);
    tg.resize(n + 1);
    bccid.resize(n + 1);
    ts.resize(n + 1, -1);
    low.resize(n + 1);
    cnt.resize(n + 1);

    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        tg[u].eb(v);
        tg[v].eb(u);
    }

    for(int i = 1; i <= n; i++){
        if(ts[i] == -1) dfst(i, i);
    }
    //printv(bccid, cerr);
    //printv(cnt, cerr);

    for(int i = 1; i <= n; i++){
        for(int j : tg[i]){
            if(bccid[i] != bccid[j]) g[bccid[i]].insert(bccid[j]);
        }
    }

    for(int i = 1; i <= n; i++){
        if(sz[i]) continue;
        dfs(i, i);
        r = sz[i];
        dfs2(i, i);
    }

    cout << ans << "\n";

    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Incorrect 1 ms 384 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 93 ms 21496 KB Output is correct
2 Correct 86 ms 21496 KB Output is correct
3 Correct 117 ms 23416 KB Output is correct
4 Correct 98 ms 21496 KB Output is correct
5 Correct 109 ms 19960 KB Output is correct
6 Correct 122 ms 24568 KB Output is correct
7 Correct 128 ms 21112 KB Output is correct
8 Correct 131 ms 22952 KB Output is correct
9 Correct 121 ms 20088 KB Output is correct
10 Correct 114 ms 19832 KB Output is correct
11 Correct 90 ms 16888 KB Output is correct
12 Correct 91 ms 16892 KB Output is correct
13 Correct 90 ms 16632 KB Output is correct
14 Correct 79 ms 16504 KB Output is correct
15 Correct 76 ms 15864 KB Output is correct
16 Correct 81 ms 15608 KB Output is correct
17 Correct 16 ms 10112 KB Output is correct
18 Correct 14 ms 10112 KB Output is correct
19 Correct 16 ms 10112 KB Output is correct
20 Correct 14 ms 10112 KB Output is correct
21 Correct 16 ms 10112 KB Output is correct
22 Correct 13 ms 10112 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 22928 KB Output is correct
2 Correct 143 ms 22904 KB Output is correct
3 Correct 148 ms 22776 KB Output is correct
4 Correct 138 ms 22776 KB Output is correct
5 Correct 138 ms 22820 KB Output is correct
6 Correct 159 ms 33656 KB Output is correct
7 Correct 180 ms 26872 KB Output is correct
8 Correct 159 ms 25848 KB Output is correct
9 Correct 152 ms 24828 KB Output is correct
10 Correct 139 ms 22716 KB Output is correct
11 Correct 170 ms 22904 KB Output is correct
12 Correct 166 ms 22904 KB Output is correct
13 Correct 139 ms 22776 KB Output is correct
14 Correct 130 ms 21752 KB Output is correct
15 Correct 124 ms 20604 KB Output is correct
16 Correct 80 ms 17144 KB Output is correct
17 Correct 124 ms 24176 KB Output is correct
18 Correct 125 ms 24172 KB Output is correct
19 Correct 125 ms 24192 KB Output is correct
20 Correct 122 ms 23892 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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