oj.uz

Submission #261370

# Submission time Handle Problem Language Result Execution time Memory
261370 2020-08-11T16:44:53 Z Hideo Duathlon (APIO18_duathlon) C++17
23 / 100
 236 ms 29432 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];
    //cout << v << ' ' << total[v] << endl;
}

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]) -
                            1LL * (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) -
                           1LL * (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:118: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 11 ms 14464 KB Output is correct
3 Correct 11 ms 14464 KB Output is correct
4 Correct 11 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 11 ms 14464 KB Output is correct
3 Correct 11 ms 14464 KB Output is correct
4 Correct 11 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 Incorrect 236 ms 29432 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 13 ms 14464 KB Output is correct
2 Correct 14 ms 14464 KB Output is correct
3 Correct 12 ms 14464 KB Output is correct
4 Correct 12 ms 14592 KB Output is correct
5 Correct 12 ms 14592 KB Output is correct
6 Correct 12 ms 14592 KB Output is correct
7 Correct 12 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 12 ms 14464 KB Output is correct
12 Correct 13 ms 14464 KB Output is correct
13 Correct 12 ms 14464 KB Output is correct
14 Correct 12 ms 14464 KB Output is correct
15 Correct 13 ms 14464 KB Output is correct
16 Correct 12 ms 14464 KB Output is correct
17 Correct 12 ms 14464 KB Output is correct
18 Correct 12 ms 14464 KB Output is correct
19 Correct 12 ms 14592 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 207 ms 20856 KB Output is correct
2 Correct 199 ms 20836 KB Output is correct
3 Correct 171 ms 20856 KB Output is correct
4 Correct 180 ms 20984 KB Output is correct
5 Correct 189 ms 20876 KB Output is correct
6 Correct 233 ms 28924 KB Output is correct
7 Correct 193 ms 26232 KB Output is correct
8 Correct 204 ms 24908 KB Output is correct
9 Correct 169 ms 23544 KB Output is correct
10 Correct 149 ms 20856 KB Output is correct
11 Correct 137 ms 20856 KB Output is correct
12 Correct 129 ms 20856 KB Output is correct
13 Correct 130 ms 20912 KB Output is correct
14 Correct 102 ms 20728 KB Output is correct
15 Correct 92 ms 20472 KB Output is correct
16 Correct 63 ms 19324 KB Output is correct
17 Correct 85 ms 20848 KB Output is correct
18 Correct 86 ms 20848 KB Output is correct
19 Correct 88 ms 20844 KB Output is correct
20 Correct 88 ms 20856 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 12 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 20924 KB Output is correct
2 Correct 156 ms 20852 KB Output is correct
3 Incorrect 155 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 11 ms 14464 KB Output is correct
2 Correct 11 ms 14464 KB Output is correct
3 Correct 11 ms 14464 KB Output is correct
4 Correct 11 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 11 ms 14464 KB Output is correct
3 Correct 11 ms 14464 KB Output is correct
4 Correct 11 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 -