oj.uz

Submission #261484

# Submission time Handle Problem Language Result Execution time Memory
261484 2020-08-11T18:56:01 Z Hideo Duathlon (APIO18_duathlon) C++17
31 / 100
 246 ms 41072 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, S5;
int h[N], d[N], sz[N], mn[N], rev[N], con[N];
int dp[N][2], mns[N][2], total[N][2];
int n, m, csz;

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

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]][0] += mns[h[to]][0];
            mns[h[v]][1] += mns[h[to]][1];
            total[v][0] += total[to][0];
            total[v][1] += total[to][1];
            mns[h[to]][0] = 0;
            mns[h[to]][1] = 0;
            temp = min(temp, mn[to]);
        }
    }
    if (temp != INF && temp != mn[v])
        spawn[temp][0].pb(v);
    if (temp != INF && temp + 1 != mn[v] && h[v] - mn[v] > 2)
        spawn[min(h[v], temp + 1)][1].pb(v);

    for (int it : despawn[h[v]][0])
        total[v][0] -= dp[it][0];
    despawn[h[v]][0].clear();

    for (int it : despawn[h[v]][1])
        total[v][1] -= dp[it][0];
    despawn[h[v]][1].clear();

    for (int it : spawn[h[v]][0]){
        total[v][0] += dp[it][0];
        despawn[mn[it]][0].pb(it);
    }
    spawn[h[v]][0].clear();

    for (int it : spawn[h[v]][1]){
        total[v][1] += dp[it][0];
        despawn[mn[it] + 1][1].pb(it);
    }
    spawn[h[v]][1].clear();

    dp[v][0] = sz[v] - 1 - mns[h[v]][0] + total[v][0];
    dp[v][1] = sz[v] - 1 - mns[h[v]][1] + total[v][1];
    mns[mn[v]][0]++;
    mns[mn[v] + 1][1]++;
    S2 += 1LL * (csz - sz[v]) * dp[v][0];
}

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]]) * (max(0, 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 * sz[to] * (h[v] - mn[to]) * s;
            s += sz[to];
            calc4(to);
        }
    }
}

void calc5 (int v){
    int s = 0;
    for (int to : g[v]){
        if (h[to] - h[v] == 1){
            calc5(to);
            con[to] += dp[to][1];
            if (mn[to] < h[v])
                con[to]++;
            s += con[to];
        }
    }
    for (int to : g[v])
        if (h[to] - h[v] == 1)
            S5 += 1LL * con[to] * (sz[v] - sz[to] - 1) * (csz - sz[v]);
}

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);
            calc5(i);
        }
    }
    //cout << S1 << ' ' << S2 << ' ' << S3 << ' ' << S4 << ' ' << S5 << endl;
    cout << S1 + 2LL * (S2 + S3 + S4 + S5);
}

Compilation message

count_triplets.cpp:152: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 17 ms 23808 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Correct 17 ms 23808 KB Output is correct
4 Correct 17 ms 23808 KB Output is correct
5 Correct 17 ms 23808 KB Output is correct
6 Correct 18 ms 23808 KB Output is correct
7 Correct 17 ms 23808 KB Output is correct
8 Incorrect 17 ms 23808 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 41072 KB Output is correct
2 Correct 201 ms 40940 KB Output is correct
3 Correct 200 ms 38644 KB Output is correct
4 Correct 246 ms 39792 KB Output is correct
5 Correct 198 ms 36084 KB Output is correct
6 Correct 195 ms 36340 KB Output is correct
7 Correct 225 ms 34428 KB Output is correct
8 Correct 218 ms 35320 KB Output is correct
9 Correct 204 ms 32720 KB Output is correct
10 Correct 206 ms 34180 KB Output is correct
11 Correct 116 ms 30968 KB Output is correct
12 Correct 114 ms 30968 KB Output is correct
13 Correct 117 ms 30968 KB Output is correct
14 Correct 103 ms 30840 KB Output is correct
15 Correct 91 ms 30200 KB Output is correct
16 Correct 82 ms 30212 KB Output is correct
17 Correct 25 ms 26496 KB Output is correct
18 Correct 23 ms 26624 KB Output is correct
19 Correct 23 ms 26496 KB Output is correct
20 Correct 23 ms 26496 KB Output is correct
21 Correct 24 ms 26368 KB Output is correct
22 Correct 23 ms 26368 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23936 KB Output is correct
2 Correct 17 ms 23936 KB Output is correct
3 Correct 18 ms 23928 KB Output is correct
4 Correct 18 ms 24192 KB Output is correct
5 Correct 18 ms 24064 KB Output is correct
6 Correct 18 ms 23936 KB Output is correct
7 Correct 18 ms 24064 KB Output is correct
8 Correct 18 ms 23936 KB Output is correct
9 Correct 17 ms 23936 KB Output is correct
10 Correct 18 ms 24056 KB Output is correct
11 Correct 17 ms 23936 KB Output is correct
12 Correct 17 ms 23936 KB Output is correct
13 Correct 17 ms 23936 KB Output is correct
14 Correct 19 ms 23936 KB Output is correct
15 Correct 18 ms 23936 KB Output is correct
16 Correct 17 ms 23972 KB Output is correct
17 Correct 17 ms 23936 KB Output is correct
18 Correct 18 ms 23936 KB Output is correct
19 Correct 18 ms 23936 KB Output is correct
20 Correct 17 ms 23936 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 31144 KB Output is correct
2 Correct 150 ms 31224 KB Output is correct
3 Correct 143 ms 31100 KB Output is correct
4 Correct 144 ms 31096 KB Output is correct
5 Correct 159 ms 31224 KB Output is correct
6 Correct 200 ms 39292 KB Output is correct
7 Correct 191 ms 36728 KB Output is correct
8 Correct 201 ms 35320 KB Output is correct
9 Correct 184 ms 33784 KB Output is correct
10 Correct 144 ms 31096 KB Output is correct
11 Correct 199 ms 31096 KB Output is correct
12 Correct 187 ms 31096 KB Output is correct
13 Correct 165 ms 31192 KB Output is correct
14 Correct 121 ms 31096 KB Output is correct
15 Correct 112 ms 30968 KB Output is correct
16 Correct 75 ms 29944 KB Output is correct
17 Correct 91 ms 30576 KB Output is correct
18 Correct 100 ms 30576 KB Output is correct
19 Correct 113 ms 30704 KB Output is correct
20 Correct 106 ms 30684 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 31172 KB Output is correct
2 Correct 146 ms 31096 KB Output is correct
3 Correct 177 ms 31096 KB Output is correct
4 Incorrect 185 ms 31736 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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