oj.uz

답안 #272664

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
272664 2020-08-18T13:10:59 Z evpipis 철인 이종 경기 (APIO18_duathlon) C++11
10 / 100
 268 ms 38764 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef long long ll;

const int len = 2e5+5;

int num[len], low[len], art[len], sz[len], vis[len], par[len], subtree[len];
int cnt_dfs, cnt_com, n, m;
ii edge[len];
vector<int> com[len], nex[len], stck;
vector<ii> adj[len];

// this dfs works fine because the graph is simple
// (no multiple edges or self loops)
void dfs(int u, int root = 0){
    num[u] = low[u] = ++cnt_dfs;

    int children = 0;
    for (auto v: adj[u]){
        if (!vis[v.se] && !num[v.fi]){
            children++;
            vis[v.se] = 1, stck.pb(v.se);
            dfs(v.fi);
            low[u] = min(low[u], low[v.fi]);

            if (low[v.fi] >= num[u]){
                cnt_com++;
                art[u] = 1;

                while (true){
                    int e = stck.back();
                    stck.pop_back();

                    com[cnt_com].pb(e);

                    if (e == v.se)
                        break;
                }
            }
        }
        else if (!vis[v.se] && num[v.fi]){
            vis[v.se] = 1, stck.pb(v.se);
            low[u] = min(low[u], num[v.fi]);
        }
    }

    if (root)
        art[u] = (children > 1);

    //printf("finished dfs: u = %d, art = %d, num = %d, low = %d\n", u, art[u], num[u], low[u]);
}

void decompose(){
    set<ii> mys;
    for (int i = 1; i <= n; i++)
        vis[i] = 0;

    for (int i = 1; i <= cnt_com; i++){
        /*
        printf("component $%d:", i);
        for (auto e: com[i])
            printf(" (%d, %d)", edge[e].fi, edge[e].se);
        printf("\n");
        */

        for (auto e: com[i]){
            int a = edge[e].fi, b = edge[e].se;
            if (!vis[a] && !art[a])
                vis[a] = 1, sz[i+n]++;
            if (!art[b] && !vis[b])
                vis[b] = 1, sz[i+n]++;

            if (art[a] && !mys.count(mp(a, i+n))){
                mys.insert(mp(a, i+n));
                nex[a].pb(i+n);
                nex[i+n].pb(a);
            }
            if (art[b] && !mys.count(mp(b, i+n))){
                mys.insert(mp(b, i+n));
                nex[b].pb(i+n);
                nex[i+n].pb(b);
            }
        }

        //printf("sz = %d\n", sz[i+n]);
    }
}

void fix(int u){
    /*
    printf("u = %d\n", u);
    if (art[u])
        printf("i am articulation point\n");
    else
        printf("i am a 2-vertext cc\n");
    */

    subtree[u] = 1;
    if (!art[u])
        subtree[u] = sz[u];
    for (auto v: nex[u]){
        if (v == par[u]) continue;

        par[v] = u;
        fix(v);
        subtree[u] += subtree[v];
    }

    //printf("ins fix: u = %d, subtree = %d\n", u, subtree[u]);
}

ll solve(int u, int all){
    //printf("u = %d, all = %d\n", u, all);
    ll ans = 0;

    for (auto v: nex[u])
        if (v != par[u])
            ans += solve(v, all);

    ll sum = 0;
    for (auto v: nex[u]){
        int sub = subtree[v];
        if (v == par[u])
            sub = all-subtree[u];

        //printf("%d -> %d, sub = %d\n", u, v, sub);
        sum += sub;
    }

    //printf("u = %d, sum = %lld\n", u, sum);

    if (art[u]){
        for (auto v: nex[u]){
            int sub = subtree[v];
            if (v == par[u])
                sub = all-subtree[u];

            // two different subtrees
            ans += sub*1LL*(sum-sub);

            // same subtree - not all cases
            ans += sz[v]*1LL*(sz[v]-1);
            ans += 2*sz[v]*1LL*(sub-sz[v]);
        }
    }
    else{
        int mul = 0;
        for (auto v: nex[u]){
            int sub = subtree[v];
            if (v == par[u])
                sub = all-subtree[u];

            mul += sub*1LL*(sum-sub);
        }

        for (auto v: nex[u]){
            int sub = subtree[v];
            if (v == par[u])
                sub = all-subtree[u];

            // two different subtrees
            ans += sz[u]*1LL*sub*1LL*(sum-sub);

            // 1 from my cc and one from a subtree
            ans += 2*sz[u]*1LL*(sz[u]-1)*1LL*sub;

            // 2 from my cc
            ans += sz[u]*1LL*(sz[u]-1)*1LL*(sz[u]-2);

            // center is adjacent art
            ans += mul - 2*sub*1LL*(sum-sub);
        }
    }

    return ans;
}

int main(){
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        adj[a].pb(mp(b, i));
        adj[b].pb(mp(a, i));
        edge[i] = mp(a, b);
    }

    for (int i = 1; i <= n; i++)
        if (!num[i])
            dfs(i, 1);
    //printf("after dfs\n");

    decompose();
    //printf("after decompose\n");

    //printf("cnt_com = %d\n", cnt_com);

    ll ans = 0;
    for (int i = 1; i <= n+cnt_com; i++)
        if ((art[i] || i >= n+1) && !par[i])
            fix(i), ans += solve(i, subtree[i]);
    //printf("after solve\n");

    printf("%lld\n", ans);
    return 0;
}
/*
4 3
1 2
2 3
3 4

4 4
1 2
2 3
3 4
4 2
*/

Compilation message

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

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 14464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 14464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 94 ms 29776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 14720 KB Output is correct
2 Correct 11 ms 14720 KB Output is correct
3 Correct 11 ms 14720 KB Output is correct
4 Correct 12 ms 14848 KB Output is correct
5 Correct 12 ms 14848 KB Output is correct
6 Correct 11 ms 14720 KB Output is correct
7 Correct 12 ms 14848 KB Output is correct
8 Correct 11 ms 14720 KB Output is correct
9 Correct 11 ms 14720 KB Output is correct
10 Correct 11 ms 14720 KB Output is correct
11 Correct 11 ms 14720 KB Output is correct
12 Correct 11 ms 14720 KB Output is correct
13 Correct 11 ms 14720 KB Output is correct
14 Correct 11 ms 14720 KB Output is correct
15 Correct 11 ms 14592 KB Output is correct
16 Correct 11 ms 14564 KB Output is correct
17 Correct 11 ms 14648 KB Output is correct
18 Correct 11 ms 14592 KB Output is correct
19 Correct 11 ms 14720 KB Output is correct
20 Correct 11 ms 14592 KB Output is correct

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 268 ms 38676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 14720 KB Output is correct
2 Correct 11 ms 14720 KB Output is correct
3 Correct 11 ms 14720 KB Output is correct
4 Incorrect 12 ms 14592 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 268 ms 38764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 14464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 14464 KB Output isn't correct
2 Halted 0 ms 0 KB -