oj.uz

Submission #218558

# Submission time Handle Problem Language Result Execution time Memory
218558 2020-04-02T09:33:38 Z VEGAnn Duathlon (APIO18_duathlon) C++14
0 / 100
 11 ms 7424 KB 
#include <bits/stdc++.h>
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 100100;
const int M = 200100;
set<int> st;
vector<int> g[N], adj[2 * N];
int n, m, tin[N], fup[N], pr[N], siz_comp[2 * N], siz[2 * N], tt = 0, U[M], V[M];
bool mrk[2 * N];
ll ans = 0ll;

int get(int x){ return (pr[x] == x ? x : pr[x] = get(pr[x])); }

void dfs0(int v, int p_edg){
    mrk[v] = 1;
    tin[v] = fup[v] = ++tt;

    for (int nm : g[v]){
        if (nm == p_edg) continue;

        int u = (U[nm] == v ? V[nm] : U[nm]);

        if (!mrk[u]){
            dfs0(u, nm);

            if (fup[u] < tin[v]){
                if (p_edg >= 0) pr[get(p_edg)] = get(nm);
            }

            fup[v] = min(fup[v], fup[u]);
        } else {
            fup[v] = min(fup[v], tin[u]);

            if (tin[u] < tin[v])
                pr[get(p_edg)] = get(nm);
        }
    }
}

void dfs(int v, int p){
    mrk[v] = 1;
    siz[v] = bool(v < n);

    for (int u : adj[v])
        if (u != p) {
            dfs(u, v);
            siz[v] += siz[u];
        }
}

void finally(int v, int r, int p){
    if (v < n){
        for (int u : adj[v]){
            assert(u >= n);

            if (u == p){
                ans -= (ll(siz_comp[u - n]) - 1ll) * (ll(siz[r]) - ll(siz[v]) - 1ll) *  (ll(siz[r]) - ll(siz[v]));
            } else {
                ans -= (ll(siz_comp[u - n]) - 1ll) * ll(siz[u]) * (ll(siz[u]) - 1ll);
            }
        }
    }

    for (int u : adj[v]){
        if (u == p) continue;
        finally(u, r, v);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    freopen("in.txt","r",stdin);

    cin >> n >> m;

    for (int i = 0; i < m; i++){
        pr[i] = i;

        int x, y; cin >> x >> y;
        x--; y--;

        U[i] = x;
        V[i] = y;
        g[x].PB(i);
        g[y].PB(i);
    }

    for (int i = 0; i < n; i++)
        if (!mrk[i]) dfs0(i, -1);

    for (int v = 0; v < n; v++){
        st.clear();

        for (int nm : g[v])
            st.insert(get(nm));

        for (auto cp : st){
            siz_comp[cp]++;
            adj[cp + n].PB(v);
            adj[v].PB(cp + n);
        }
    }

    fill(mrk, mrk + n, 0);

    for (int v = 0; v < n; v++){
        if (mrk[v]) continue;

        dfs(v, -1);
        ans += ll(siz[v]) * (ll(siz[v]) - 1ll) * (ll(siz[v]) - 2ll);
        finally(v, v, -1);
    }

    cout << ans;

    return 0;
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:74:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("in.txt","r",stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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