oj.uz

Submission #260924

# Submission time Handle Problem Language Result Execution time Memory
260924 2020-08-11T08:06:01 Z wiwiho Duathlon (APIO18_duathlon) C++14
23 / 100
 204 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] + i * (cnt[now] - 1) * (cnt[now] - 1) * 2 + i * (cnt[now] - 1) * 2;
    }
    ans += cnt[now] * (cnt[now] - 1) * (cnt[now] - 2) / 3;
}

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 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 21496 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 2 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 1 ms 640 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 2 ms 512 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Correct 1 ms 512 KB Output is correct
17 Correct 3 ms 512 KB Output is correct
18 Correct 1 ms 512 KB Output is correct
19 Correct 2 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 204 ms 22776 KB Output is correct
2 Correct 195 ms 22752 KB Output is correct
3 Correct 180 ms 22776 KB Output is correct
4 Correct 173 ms 22880 KB Output is correct
5 Correct 153 ms 22776 KB Output is correct
6 Correct 176 ms 33656 KB Output is correct
7 Correct 173 ms 27004 KB Output is correct
8 Correct 172 ms 25848 KB Output is correct
9 Correct 162 ms 24824 KB Output is correct
10 Correct 145 ms 22776 KB Output is correct
11 Correct 152 ms 22776 KB Output is correct
12 Correct 146 ms 22780 KB Output is correct
13 Correct 159 ms 22776 KB Output is correct
14 Correct 130 ms 21756 KB Output is correct
15 Correct 126 ms 20620 KB Output is correct
16 Correct 70 ms 17144 KB Output is correct
17 Correct 115 ms 24176 KB Output is correct
18 Correct 116 ms 24172 KB Output is correct
19 Correct 123 ms 24172 KB Output is correct
20 Correct 163 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 2 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 152 ms 22776 KB Output is correct
2 Correct 168 ms 22772 KB Output is correct
3 Incorrect 148 ms 19960 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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