oj.uz

Submission #372734

# Submission time Handle Problem Language Result Execution time Memory
372734 2021-03-01T11:56:09 Z BartolM Duathlon (APIO18_duathlon) C++17
31 / 100
 154 ms 19176 KB 
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=1e5+5;

int n, m, dtime=1;
ll sol=0;
int cnt[N], siz[N], P[N];
int dt[N], lw[N];
vector <int> ls[N], ls2[N];
vector <pii> ed;
#define DEBUG 0

int name(int x) {
    if (x==P[x]) return x;
    P[x]=name(P[x]);
    return P[x];
}

void mrg(int a, int b) {
    a=name(a); b=name(b);
    if (a==b) return;
    P[a]=b;
    siz[b]+=siz[a];
}

void rek(int node, int par) {
    dt[node]=dtime++;
    lw[node]=dt[node];
    for (int sus:ls[node]) {
        if (sus==par) continue;
        if (dt[sus]==0) {
            rek(sus, node);
            lw[node]=min(lw[node], lw[sus]);
        }
        else { //backedge
            lw[node]=min(lw[node], dt[sus]);
        }
    }
    if (par && lw[node]==dt[node]) { //bridge
        ed.pb(mp(node, par));
        #if DEBUG
            printf("bridge %d -> %d\n", node, par);
        #endif
    }
    else if (par) {
        mrg(node, par);
        #if DEBUG
            printf("mrgam %d i %d\n", node, par);
        #endif
    }
}

void dfs(int node, int par) {
    cnt[node]=siz[node];
    for (int sus:ls2[node]) {
        if (sus==par) continue;
        dfs(sus, node);
        cnt[node]+=cnt[sus];
    }
}

void calc(int node, int par, int uk) {
    sol+=(ll)siz[node]*(siz[node]-1)*(siz[node]-2);
    int iz=uk-siz[node];
    for (int sus:ls2[node]) {
        if (sus==par) continue;
        calc(sus, node, uk);
        iz-=cnt[sus];
        sol+=(ll)cnt[sus]*(uk-cnt[sus]-siz[node])*siz[node];


        if (siz[node]>2) sol+=(ll)cnt[sus]*(siz[node]-1)*(siz[node]-1)*2;
    }
    sol+=(ll)iz*(uk-iz-siz[node])*siz[node];
    if (siz[node]>2) sol+=(ll)iz*(siz[node]-1)*(siz[node]-1)*2;
}

void solve() {
    for (int i=1; i<=n; ++i) P[i]=i, siz[i]=1;
    for (int i=1; i<=n; ++i) {
        if (dt[i]) continue;
        dtime=1;
        ed.clear();
        rek(i, 0);
        for (pii pp:ed) {
            ls2[name(pp.X)].pb(name(pp.Y));
            ls2[name(pp.Y)].pb(name(pp.X));
        }
    }

    for (int i=1; i<=n; ++i) {
        sort(ls2[i].begin(), ls2[i].end());
        ls2[i].erase(unique(ls2[i].begin(), ls2[i].end()), ls2[i].end());

        #if DEBUG
            printf("node: %d, siz: %d, sus: ", i, siz[i]);
            for (int sus:ls2[i]) printf("%d ", sus);
            printf("\n");
        #endif // DEBUG
    }

    for (int i=1; i<=n; ++i) {
        if (cnt[i] || P[i]!=i) continue;
        dfs(i, 0);
        calc(i, 0, cnt[i]);
    }
    printf("%lld\n", sol);
}

void load() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<m; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        ls[a].pb(b); ls[b].pb(a);
    }
}

int main() {
    load();
    solve();
    return 0;
}

/*
8 7
2 4
4 7
6 8
3 8
5 6
5 8
6 7
*/

Compilation message

count_triplets.cpp: In function 'void load()':
count_triplets.cpp:124:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  124 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:127:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  127 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 19052 KB Output is correct
2 Correct 80 ms 19052 KB Output is correct
3 Correct 100 ms 16748 KB Output is correct
4 Correct 91 ms 18160 KB Output is correct
5 Correct 106 ms 14572 KB Output is correct
6 Correct 95 ms 15340 KB Output is correct
7 Correct 125 ms 14080 KB Output is correct
8 Correct 118 ms 14956 KB Output is correct
9 Correct 95 ms 13036 KB Output is correct
10 Correct 102 ms 13680 KB Output is correct
11 Correct 97 ms 11756 KB Output is correct
12 Correct 89 ms 11628 KB Output is correct
13 Correct 81 ms 11756 KB Output is correct
14 Correct 86 ms 11500 KB Output is correct
15 Correct 60 ms 11372 KB Output is correct
16 Correct 55 ms 11104 KB Output is correct
17 Correct 7 ms 7020 KB Output is correct
18 Correct 9 ms 7020 KB Output is correct
19 Correct 8 ms 7020 KB Output is correct
20 Correct 8 ms 7020 KB Output is correct
21 Correct 7 ms 7020 KB Output is correct
22 Correct 7 ms 7020 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 14184 KB Output is correct
2 Correct 98 ms 14312 KB Output is correct
3 Correct 154 ms 14212 KB Output is correct
4 Correct 130 ms 14220 KB Output is correct
5 Correct 112 ms 14340 KB Output is correct
6 Correct 148 ms 19176 KB Output is correct
7 Correct 149 ms 17384 KB Output is correct
8 Correct 129 ms 16616 KB Output is correct
9 Correct 141 ms 15716 KB Output is correct
10 Correct 119 ms 14060 KB Output is correct
11 Correct 110 ms 14180 KB Output is correct
12 Correct 126 ms 13676 KB Output is correct
13 Correct 114 ms 13676 KB Output is correct
14 Correct 109 ms 13292 KB Output is correct
15 Correct 129 ms 13036 KB Output is correct
16 Correct 60 ms 11756 KB Output is correct
17 Correct 82 ms 14820 KB Output is correct
18 Correct 107 ms 14812 KB Output is correct
19 Correct 79 ms 14936 KB Output is correct
20 Correct 79 ms 14816 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 14308 KB Output is correct
2 Correct 113 ms 14176 KB Output is correct
3 Incorrect 116 ms 12896 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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