oj.uz

Submission #261417

# Submission time Handle Problem Language Result Execution time Memory
261417 2020-08-11T17:29:52 Z Hideo Duathlon (APIO18_duathlon) C++17
23 / 100
 206 ms 29440 KB 
//1610612741, 1000000007
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC optimize ("Ofast")
//#pragma GCC target ("avx,avx2,fma")

#include <bits/stdc++.h>
using namespace std;

#define all(s) s.begin(), s.end()
#define ok puts("ok")
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define pi pair < int, int >
#define pii pair < int, pi >
#define next next123
#define left left123

const int N = 2e5 + 7;
const int INF = 1e9 + 7;

ll S1, S2, S3, S4;
int h[N], d[N], sz[N], mn[N], rev[N], dp[N], mns[N], total[N];
int n, m, csz;

vi g[N], despawn[N], spawn[N];

void precalc (int v, int p = 0){
    h[v] = h[p] + 1;
    sz[v] = 1;
    mn[v] = h[v];
    for (int to : g[v]){
        if (!h[to]){
            precalc(to, v);
            sz[v] += sz[to];
            mn[v] = min(mn[v], mn[to]);
        }
        else {
            mn[v] = min(mn[v], h[to]);
        }
    }
}

void calc1 (int v){
    for (int to : g[v]){
        if (h[to] - h[v] == 1){
            calc1(to);
            S1 += 1LL * (csz - sz[to] - 1) * sz[to];
        }
    }
    S1 += 1LL * (csz - sz[v]) * (sz[v] - 1);
}

void calc2 (int v){
    int temp = INF;
    for (int to : g[v]){
        if (h[to] - h[v] == 1){
            calc2(to);
            mns[h[v]] += mns[h[to]];
            total[v] += total[to];
            mns[h[to]] = 0;
            temp = min(temp, mn[to]);
        }
    }
    if (temp != INF && temp != mn[v])
        spawn[temp].pb(v);
    for (int it : despawn[h[v]])
        total[v] -= dp[it];
    despawn[h[v]].clear();
    for (int it : spawn[h[v]]){
        total[v] += dp[it];
        despawn[mn[it]].pb(it);
    }
    spawn[h[v]].clear();
    mns[mn[v]]++;
    dp[v] = sz[v] - 1 - mns[h[v]] + total[v];
    S2 += 1LL * (csz - sz[v]) * dp[v];
}

bool comp (int a, int b){
    return mn[a] > mn[b];
}

void calc3 (int v){
    rev[h[v]] = v;
    for (int to : g[v]){
        if (h[to] - h[v] == 1){
            calc3(to);
            S3 += 1LL * sz[to] * ((h[v] - mn[v] - 1) * (h[v] - mn[v]) - (h[v] - mn[to] - 1) * (h[v] - mn[to])) / 2;
            S3 += 1LL * sz[to] * (mn[v] - mn[rev[mn[v] + 1]]) * (h[v] - mn[v] - 1) - (mn[rev[mn[to] + 1]] - mn[v]) * (max(0, h[v] - mn[to] - 1));
        }
    }
    S3 += 1LL * (h[v] - mn[v] - 1) * (h[v] - mn[v]) / 2;
    S3 += 1LL * (mn[v] - mn[rev[mn[v] + 1]]) * (h[v] - mn[v] - 1);
}

void calc4 (int v){
    int s = 0;
    sort(all(g[v]), comp);
    for (int to : g[v]){
        if (h[to] - h[v] == 1){
            if (mn[to] < h[v])
                S4 += 1LL * (h[v] - mn[to]) * s;
            s += sz[to];
            calc4(to);
        }
    }
}

main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        int a, b;
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }
    for (int i = 1; i <= n; i++)
        if (!h[i])
            precalc(i);

    for (int i = 1; i <= n; i++){
        if (h[i] == 1){
            csz = sz[i];
            calc1(i);
            calc2(i);
            calc3(i);
            calc4(i);
        }
    }
    //cout << S1 << ' ' << S2 << ' ' << S3 << ' ' << S4 << endl;
    cout << S1 + 2LL * (S2 + S3 + S4);
}

Compilation message

count_triplets.cpp:115:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 29432 KB Output is correct
2 Correct 165 ms 29440 KB Output is correct
3 Correct 192 ms 27768 KB Output is correct
4 Correct 166 ms 28152 KB Output is correct
5 Correct 180 ms 25500 KB Output is correct
6 Correct 206 ms 25720 KB Output is correct
7 Correct 148 ms 23708 KB Output is correct
8 Correct 158 ms 24568 KB Output is correct
9 Correct 135 ms 22320 KB Output is correct
10 Correct 140 ms 23288 KB Output is correct
11 Correct 89 ms 20600 KB Output is correct
12 Correct 96 ms 20472 KB Output is correct
13 Correct 90 ms 20344 KB Output is correct
14 Incorrect 87 ms 20344 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 20856 KB Output is correct
2 Correct 134 ms 20856 KB Output is correct
3 Correct 126 ms 20956 KB Output is correct
4 Correct 134 ms 20856 KB Output is correct
5 Correct 130 ms 20856 KB Output is correct
6 Correct 184 ms 28820 KB Output is correct
7 Correct 197 ms 26232 KB Output is correct
8 Correct 165 ms 24824 KB Output is correct
9 Correct 193 ms 23416 KB Output is correct
10 Correct 160 ms 20856 KB Output is correct
11 Correct 151 ms 20844 KB Output is correct
12 Correct 125 ms 20856 KB Output is correct
13 Correct 116 ms 20856 KB Output is correct
14 Correct 93 ms 20728 KB Output is correct
15 Correct 90 ms 20444 KB Output is correct
16 Correct 54 ms 19320 KB Output is correct
17 Correct 78 ms 20848 KB Output is correct
18 Correct 93 ms 20976 KB Output is correct
19 Correct 75 ms 20972 KB Output is correct
20 Correct 79 ms 20860 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 20984 KB Output is correct
2 Correct 140 ms 20860 KB Output is correct
3 Incorrect 137 ms 21112 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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