oj.uz

Submission #261174

# Submission time Handle Problem Language Result Execution time Memory
261174 2020-08-11T13:21:53 Z Hideo Duathlon (APIO18_duathlon) C++17
31 / 100
 236 ms 17304 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], flg[N];
int n, m, csz;

vi g[N];

void precalc (int v, int p = 0){
    h[v] = h[p] + 1;
    sz[v] = 1;
    for (int to : g[v]){
        if (!h[to]){
            precalc(to, v);
            sz[v] += sz[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);
}

int calc2 (int v){
    mn[v] = h[v];
    int c = 0;
    for (int to : g[v]){
        if (h[to] - h[v] == 1){
            c += calc2(to);
            mn[v] = min(mn[v], mn[to]);
        }
        else
            mn[v] = min(mn[v], h[to]);
    }
    S2 += 1LL * c * (csz - sz[v]);
    c -= d[h[v]];
    if (mn[v] + 1 < h[v]){
        d[mn[v] + 1]++;
        c++;
    }
    return c;
}

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

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

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 + 2LL * (S2 + S3 + S4);
}

Compilation message

count_triplets.cpp:103: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 Incorrect 4 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 16120 KB Output is correct
2 Correct 178 ms 17304 KB Output is correct
3 Correct 209 ms 14072 KB Output is correct
4 Correct 198 ms 15608 KB Output is correct
5 Correct 236 ms 13112 KB Output is correct
6 Correct 153 ms 13048 KB Output is correct
7 Correct 146 ms 12280 KB Output is correct
8 Correct 148 ms 12792 KB Output is correct
9 Correct 127 ms 11564 KB Output is correct
10 Correct 152 ms 12240 KB Output is correct
11 Correct 115 ms 10872 KB Output is correct
12 Correct 102 ms 10688 KB Output is correct
13 Correct 68 ms 10488 KB Output is correct
14 Correct 74 ms 10488 KB Output is correct
15 Correct 48 ms 9848 KB Output is correct
16 Correct 51 ms 9836 KB Output is correct
17 Correct 8 ms 6656 KB Output is correct
18 Correct 7 ms 6528 KB Output is correct
19 Correct 7 ms 6528 KB Output is correct
20 Correct 7 ms 6528 KB Output is correct
21 Correct 8 ms 6400 KB Output is correct
22 Correct 7 ms 6400 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 9848 KB Output is correct
2 Correct 128 ms 9848 KB Output is correct
3 Correct 113 ms 9848 KB Output is correct
4 Correct 134 ms 9928 KB Output is correct
5 Correct 161 ms 9848 KB Output is correct
6 Correct 236 ms 13304 KB Output is correct
7 Correct 206 ms 12024 KB Output is correct
8 Correct 190 ms 11384 KB Output is correct
9 Correct 222 ms 10872 KB Output is correct
10 Correct 188 ms 9848 KB Output is correct
11 Correct 162 ms 9848 KB Output is correct
12 Correct 142 ms 9848 KB Output is correct
13 Correct 137 ms 9848 KB Output is correct
14 Correct 85 ms 9720 KB Output is correct
15 Correct 87 ms 9592 KB Output is correct
16 Correct 52 ms 8952 KB Output is correct
17 Correct 71 ms 9712 KB Output is correct
18 Correct 63 ms 9840 KB Output is correct
19 Correct 66 ms 9708 KB Output is correct
20 Correct 82 ms 9720 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 9832 KB Output is correct
2 Correct 135 ms 9848 KB Output is correct
3 Incorrect 131 ms 9816 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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