oj.uz

Submission #261167

# Submission time Handle Problem Language Result Execution time Memory
261167 2020-08-11T13:09:38 Z Hideo Duathlon (APIO18_duathlon) C++17
23 / 100
 211 ms 17252 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);
        }
    }
    if (!flg[v])
        S3 += 1LL * (h[v] - mn[v] - 1) * (h[v] - mn[v]) / 2;
    sort(all(g[v]), comp);
}

void calc4 (int v){
    int s = 0;
    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:104: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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 184 ms 17252 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 4 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 5 ms 5120 KB Output is correct
4 Correct 5 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 5 ms 5120 KB Output is correct
11 Correct 6 ms 5248 KB Output is correct
12 Correct 4 ms 5120 KB Output is correct
13 Correct 4 ms 5120 KB Output is correct
14 Correct 5 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 5 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 115 ms 11128 KB Output is correct
2 Correct 120 ms 11128 KB Output is correct
3 Correct 117 ms 11132 KB Output is correct
4 Correct 117 ms 11128 KB Output is correct
5 Correct 116 ms 11128 KB Output is correct
6 Correct 199 ms 14512 KB Output is correct
7 Correct 126 ms 13304 KB Output is correct
8 Correct 129 ms 12664 KB Output is correct
9 Correct 192 ms 12408 KB Output is correct
10 Correct 148 ms 11128 KB Output is correct
11 Correct 136 ms 11256 KB Output is correct
12 Correct 126 ms 11128 KB Output is correct
13 Correct 117 ms 11128 KB Output is correct
14 Correct 112 ms 10824 KB Output is correct
15 Correct 98 ms 10632 KB Output is correct
16 Correct 62 ms 9592 KB Output is correct
17 Correct 74 ms 10984 KB Output is correct
18 Correct 89 ms 10992 KB Output is correct
19 Correct 99 ms 10988 KB Output is correct
20 Correct 135 ms 11000 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5120 KB Output is correct
2 Correct 5 ms 5152 KB Output is correct
3 Incorrect 6 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 208 ms 11128 KB Output is correct
2 Correct 211 ms 11000 KB Output is correct
3 Incorrect 203 ms 11260 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 -