oj.uz

Submission #217952

# Submission time Handle Problem Language Result Execution time Memory
217952 2020-03-31T10:06:15 Z perveevm Duathlon (APIO18_duathlon) C++14
10 / 100
 1000 ms 29432 KB 
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

#ifdef PERVEEVM_LOCAL
    #define debug(x) std::cerr << (#x) << ":\t" << (x) << std::endl
#else
    #define debug(x) 238;
#endif

#define fastIO std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0)
#define NAME "File"

using ll = long long;
using ld = long double;

#ifdef PERVEEVM_LOCAL
    std::mt19937 rnd(238);
#else
    std::mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

const double PI = atan2(0.0, -1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = (ll)2e18;
const int N = 200100;
const int LG = 18;

std::vector<int> g[N];
bool used[N];
int cmpId[N];
int sz = 0, curCmp = 0, timer = 0;
int dp[LG][N];
int tin[N], tout[N];
int h[N];

void dfs(int v, int p, int d) {
    used[v] = true;
    ++sz;
    cmpId[v] = curCmp;
    tin[v] = timer++;
    h[v] = d;

    dp[0][v] = p;

    for (auto to : g[v]) {
        if (!used[to]) {
            dfs(to, v, d + 1);
        }
    }

    tout[v] = timer++;
}

void precalcLCA() {
    for (int i = 1; i < LG; ++i) {
        for (int j = 0; j < N; ++j) {
            dp[i][j] = dp[i - 1][dp[i - 1][j]];
        }
    }
}

bool isParent(int a, int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b) {
    if (isParent(a, b)) {
        return a;
    }
    if (isParent(b, a)) {
        return b;
    }

    for (int i = LG - 1; i >= 0; --i) {
        int pa = dp[i][a];

        if (!isParent(pa, b)) {
            a = pa;
        }
    }

    return dp[0][a];
}

int dist(int a, int b) {
    return h[a] + h[b] - 2 * h[lca(a, b)];
}

void run() {
    int n, m;
    scanf("%d%d", &n, &m);

    for (int i = 0; i < m; ++i) {
        int from, to;
        scanf("%d%d", &from, &to);

        g[from - 1].push_back(to - 1);
        g[to - 1].push_back(from - 1);
    }

    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            dfs(i, i, 0);
            ++curCmp;
        }
    }

    precalcLCA();

    ll ans = 0;
    for (int from = 0; from < n; ++from) {
        for (int to = 0; to < n; ++to) {
            if (from == to || cmpId[from] != cmpId[to]) {
                continue;
            }

            ans += dist(from, to) - 1;
        }
    }

    printf("%lld\n", ans);
}

int main(void) {
    // freopen(NAME".in", "r", stdin);
    // freopen(NAME".out", "w", stdout);

    auto start = std::chrono::high_resolution_clock::now();
    run();
    auto end = std::chrono::high_resolution_clock::now();

    #ifdef PERVEEVM_LOCAL
        std::cerr << "Execution time: "
                  << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
                  << " ms" << std::endl;
    #endif

    return 0;
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:132:10: warning: variable 'start' set but not used [-Wunused-but-set-variable]
     auto start = std::chrono::high_resolution_clock::now();
          ^~~~~
count_triplets.cpp:134:10: warning: variable 'end' set but not used [-Wunused-but-set-variable]
     auto end = std::chrono::high_resolution_clock::now();
          ^~~
count_triplets.cpp: In function 'void run()':
count_triplets.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
count_triplets.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &from, &to);
         ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 29432 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 18432 KB Output is correct
2 Correct 94 ms 18432 KB Output is correct
3 Correct 97 ms 18432 KB Output is correct
4 Correct 50 ms 18432 KB Output is correct
5 Correct 71 ms 18552 KB Output is correct
6 Correct 79 ms 18432 KB Output is correct
7 Correct 58 ms 18432 KB Output is correct
8 Correct 75 ms 18432 KB Output is correct
9 Correct 81 ms 18432 KB Output is correct
10 Correct 85 ms 18432 KB Output is correct
11 Correct 84 ms 18552 KB Output is correct
12 Correct 54 ms 18432 KB Output is correct
13 Correct 33 ms 18464 KB Output is correct
14 Correct 20 ms 18432 KB Output is correct
15 Correct 19 ms 18432 KB Output is correct
16 Correct 18 ms 18432 KB Output is correct
17 Correct 94 ms 18552 KB Output is correct
18 Correct 97 ms 18432 KB Output is correct
19 Correct 96 ms 18432 KB Output is correct
20 Correct 96 ms 18432 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1096 ms 24952 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 18432 KB Output is correct
2 Correct 102 ms 18480 KB Output is correct
3 Incorrect 99 ms 18432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 24952 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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