oj.uz

Submission #261418

# Submission time Handle Problem Language Result Execution time Memory
261418 2020-08-11T17:34:03 Z Hideo Duathlon (APIO18_duathlon) C++17
31 / 100
 190 ms 28280 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]]) * (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 * (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 11 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Correct 11 ms 14464 KB Output is correct
4 Correct 10 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 11 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Correct 11 ms 14464 KB Output is correct
4 Correct 10 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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 28152 KB Output is correct
2 Correct 168 ms 28280 KB Output is correct
3 Correct 172 ms 26360 KB Output is correct
4 Correct 165 ms 27128 KB Output is correct
5 Correct 163 ms 24076 KB Output is correct
6 Correct 171 ms 24500 KB Output is correct
7 Correct 150 ms 22520 KB Output is correct
8 Correct 160 ms 23416 KB Output is correct
9 Correct 147 ms 21112 KB Output is correct
10 Correct 144 ms 22008 KB Output is correct
11 Correct 92 ms 19452 KB Output is correct
12 Correct 88 ms 19448 KB Output is correct
13 Correct 83 ms 19448 KB Output is correct
14 Correct 79 ms 19320 KB Output is correct
15 Correct 67 ms 19704 KB Output is correct
16 Correct 64 ms 19576 KB Output is correct
17 Correct 19 ms 16384 KB Output is correct
18 Correct 15 ms 16384 KB Output is correct
19 Correct 15 ms 16256 KB Output is correct
20 Correct 15 ms 16256 KB Output is correct
21 Correct 15 ms 16256 KB Output is correct
22 Correct 16 ms 16256 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 19668 KB Output is correct
2 Correct 130 ms 19704 KB Output is correct
3 Correct 125 ms 19704 KB Output is correct
4 Correct 124 ms 19704 KB Output is correct
5 Correct 125 ms 19660 KB Output is correct
6 Correct 190 ms 27768 KB Output is correct
7 Correct 174 ms 24952 KB Output is correct
8 Correct 158 ms 23548 KB Output is correct
9 Correct 154 ms 22264 KB Output is correct
10 Correct 127 ms 19576 KB Output is correct
11 Correct 133 ms 19704 KB Output is correct
12 Correct 116 ms 19704 KB Output is correct
13 Correct 118 ms 19656 KB Output is correct
14 Correct 96 ms 19576 KB Output is correct
15 Correct 85 ms 19452 KB Output is correct
16 Correct 57 ms 18816 KB Output is correct
17 Correct 75 ms 19568 KB Output is correct
18 Correct 80 ms 19568 KB Output is correct
19 Correct 75 ms 19564 KB Output is correct
20 Correct 85 ms 19576 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14464 KB Output is correct
2 Correct 11 ms 14464 KB Output is correct
3 Incorrect 11 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 145 ms 19700 KB Output is correct
2 Correct 143 ms 19576 KB Output is correct
3 Incorrect 177 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 11 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Correct 11 ms 14464 KB Output is correct
4 Correct 10 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 11 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Correct 11 ms 14464 KB Output is correct
4 Correct 10 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 -