oj.uz

Submission #108880

# Submission time Handle Problem Language Result Execution time Memory
108880 2019-05-02T10:53:40 Z oolimry Duathlon (APIO18_duathlon) C++14
66 / 100
 511 ms 58348 KB 
#include <bits/stdc++.h>

using namespace std;
int n, m;
typedef vector<int> vi;
typedef pair<int,int> ii;
struct node{
    int num;
    int low;
    int parent;
    bool vis = false;
    bool isArti = false;
    vi adj;
};

vector<unordered_set<int> > biconnected;
stack<int> s; ///this is only needed for biconnected components
///note: this will ignore single nodes with no edges
static node g[200005];
int rootChildren = 0;
int root = 0;
int cnt = 0;
void dfs(int u){
    g[u].vis = true;
    g[u].low = cnt;
    g[u].num = cnt;
    cnt++;
    for(int i = 0;i < g[u].adj.size();i++){
        int v = g[u].adj[i];
        if(!g[v].vis){
            g[v].parent = u;
            if(u == root) rootChildren++;
            s.push(u); ///s traces the path of tree traversal
            dfs(v);
            g[u].low = min(g[u].low,g[v].low);

            if(g[v].low >= g[u].num){
                g[u].isArti = true;
                g[u].low = min(g[u].low,g[v].low);
                unordered_set<int> newSet;
                int nn;
                biconnected.push_back(newSet); ///create new biconnected component
                do{
                    nn = s.top();
                    s.pop();
                    biconnected.back().insert(nn);
                }while(nn != u);
            }
            ///if(g[v].low > g[u].num){
                  ///u,v is a bridge
            ///}
        }
        else if(v != g[u].parent){
            g[u].low = min(g[u].low,g[v].low);
        }
        s.push(u);
    }
}
struct node2{
    long long sz;
    long long dp = 0;
    bool isArti = false;
    bool vis = false;
    int p = -1;
    vi adj;
};

vector<node2> bct; ///block-cut tree
long long ans = 0ll;
long long dp(int u, int p){
    bct[u].dp = bct[u].sz;
    for(int j = 0;j < bct[u].adj.size();j++){
        int v = bct[u].adj[j];
        if(v != p)
            bct[u].dp += dp(v,u);
    }
    return bct[u].dp;
}
void countWays(int u, long long total){
    long long sz = bct[u].sz;
    //if(bct[u].vis) return;
    bct[u].vis = true;
    if(!bct[u].isArti){
        ans += sz * (sz - 1) * (sz + bct[u].adj.size() - 2);
        ans += 2ll * sz * (sz + bct[u].adj.size() - 2) * (total - sz);
    }
    long long others = total - bct[u].dp;
    for(int j = 0;j < bct[u].adj.size();j++){
        int v = bct[u].adj[j];
        if(!bct[v].vis){
            countWays(v,total);
            long long extra = 0ll;
            if(!bct[u].isArti) extra = bct[u].adj.size()-2;
            ans += 2ll * (bct[u].sz + extra) * bct[v].dp * others;
            others += bct[v].dp;
        }
    }
}
int main()
{
    //freopen("i.txt","r",stdin);
    cin >> n >> m;
    ii edges[m];
    for(int i = 0;i < m;i++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a].adj.push_back(b);
        g[b].adj.push_back(a);
        edges[i] = ii(a,b);
    }

    for(int i = 0;i < n;i++){
        if(!g[i].vis){
            rootChildren = 0;
            root = i;
            dfs(i);
            if(rootChildren > 1) g[i].isArti = true;
            else g[i].isArti = false; ///this line is needed
        }
    }
    unordered_map<int,int> artis;
    for(int i = 0;i < n;i++){
        if(g[i].isArti){
            artis[i] = bct.size();
            node2 nn;
            nn.sz = 1;
            nn.isArti = true;
            bct.push_back(nn);
        }
    }

    vi components[n];
    for(int i = 0;i < biconnected.size();i++){
        node2 nn;
        nn.isArti = false;
        nn.sz = biconnected[i].size();
        bct.push_back(nn);
        for(int j : biconnected[i]){
            components[j].push_back(i+artis.size());
        }
    }

    for(int i = 0;i < n;i++){
        if(components[i].size() > 1){
            for(int j = 0;j < components[i].size();j++){
                int v = components[i][j];
                bct[v].sz--;
                bct[v].adj.push_back(artis[i]);
                bct[artis[i]].adj.push_back(v);
            }
        }
    }




    for(int i = 0;i < bct.size();i++){
        if(!bct[i].vis) countWays(i,dp(i,-1));
    }
    /*
    long long ans = 0ll;
    for(int i = 0;i < bct.size();i++){
        long long total = bct[bct[i].r].dp - bct[i].sz;
        long long sz = bct[i].sz;
        if(!bct[i].isArti){
            ans += sz * (sz - 1) * (sz + bct[i].adj.size() - 2);
            ans += 2ll * sz * (sz + bct[i].adj.size() - 2) * total;
        }
        long long others = bct[bct[i].r].dp - bct[i].dp;
        for(int j = 0;j < bct[i].adj.size();j++){
            int v = bct[i].adj[j];
            if(v != bct[i].p){
                long long extra = 0ll;
                if(!bct[i].isArti) extra = bct[i].adj.size()-2;
                ans += 2ll * (bct[i].sz + extra) * bct[v].dp * others;
                others += bct[v].dp;
            }
        }


        //if(!bct[i].isArti) ans += (bct[i].sz) * (bct[i].sz - 1) * (bct[i].adj.size());
        //cout << i << " " << ans << "\n";
    }
    */
    cout << ans;
}

/*
8 7
8 5
8 1
7 5
8 6
3 1
3 2
8 3
*/
/*
10 12
6 4
10 3
4 2
4 1
4 3
6 5
9 1
9 4
2 1
9 3
8 5
7 2
*/

Compilation message

count_triplets.cpp: In function 'void dfs(int)':
count_triplets.cpp:28:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < g[u].adj.size();i++){
                   ~~^~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'long long int dp(int, int)':
count_triplets.cpp:72:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0;j < bct[u].adj.size();j++){
                   ~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void countWays(int, long long int)':
count_triplets.cpp:88:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0;j < bct[u].adj.size();j++){
                   ~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:135:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < biconnected.size();i++){
                   ~~^~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:147:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0;j < components[i].size();j++){
                           ~~^~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:159:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < bct.size();i++){
                   ~~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8192 KB Output is correct
2 Correct 9 ms 8192 KB Output is correct
3 Correct 11 ms 8192 KB Output is correct
4 Correct 11 ms 8192 KB Output is correct
5 Correct 10 ms 8192 KB Output is correct
6 Correct 10 ms 8192 KB Output is correct
7 Correct 10 ms 8192 KB Output is correct
8 Correct 12 ms 8192 KB Output is correct
9 Correct 10 ms 8192 KB Output is correct
10 Correct 9 ms 8192 KB Output is correct
11 Correct 10 ms 8192 KB Output is correct
12 Correct 8 ms 8192 KB Output is correct
13 Correct 10 ms 8192 KB Output is correct
14 Correct 8 ms 8192 KB Output is correct
15 Correct 9 ms 8192 KB Output is correct
16 Correct 9 ms 8192 KB Output is correct
17 Correct 10 ms 8192 KB Output is correct
18 Correct 10 ms 8192 KB Output is correct
19 Correct 10 ms 8192 KB Output is correct
20 Correct 10 ms 8192 KB Output is correct
21 Correct 9 ms 8192 KB Output is correct
22 Incorrect 10 ms 8192 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8192 KB Output is correct
2 Correct 9 ms 8192 KB Output is correct
3 Correct 11 ms 8192 KB Output is correct
4 Correct 11 ms 8192 KB Output is correct
5 Correct 10 ms 8192 KB Output is correct
6 Correct 10 ms 8192 KB Output is correct
7 Correct 10 ms 8192 KB Output is correct
8 Correct 12 ms 8192 KB Output is correct
9 Correct 10 ms 8192 KB Output is correct
10 Correct 9 ms 8192 KB Output is correct
11 Correct 10 ms 8192 KB Output is correct
12 Correct 8 ms 8192 KB Output is correct
13 Correct 10 ms 8192 KB Output is correct
14 Correct 8 ms 8192 KB Output is correct
15 Correct 9 ms 8192 KB Output is correct
16 Correct 9 ms 8192 KB Output is correct
17 Correct 10 ms 8192 KB Output is correct
18 Correct 10 ms 8192 KB Output is correct
19 Correct 10 ms 8192 KB Output is correct
20 Correct 10 ms 8192 KB Output is correct
21 Correct 9 ms 8192 KB Output is correct
22 Incorrect 10 ms 8192 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 35020 KB Output is correct
2 Correct 236 ms 34812 KB Output is correct
3 Correct 401 ms 42472 KB Output is correct
4 Correct 328 ms 38976 KB Output is correct
5 Correct 296 ms 35956 KB Output is correct
6 Correct 390 ms 42156 KB Output is correct
7 Correct 367 ms 42032 KB Output is correct
8 Correct 332 ms 42548 KB Output is correct
9 Correct 338 ms 41444 KB Output is correct
10 Correct 301 ms 38332 KB Output is correct
11 Correct 214 ms 32708 KB Output is correct
12 Correct 220 ms 32700 KB Output is correct
13 Correct 201 ms 32196 KB Output is correct
14 Correct 194 ms 31808 KB Output is correct
15 Correct 157 ms 26308 KB Output is correct
16 Correct 143 ms 26052 KB Output is correct
17 Correct 12 ms 10624 KB Output is correct
18 Correct 13 ms 10624 KB Output is correct
19 Correct 13 ms 10496 KB Output is correct
20 Correct 15 ms 10496 KB Output is correct
21 Correct 12 ms 10496 KB Output is correct
22 Correct 12 ms 10496 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8548 KB Output is correct
2 Correct 10 ms 8576 KB Output is correct
3 Correct 10 ms 8576 KB Output is correct
4 Correct 11 ms 8704 KB Output is correct
5 Correct 11 ms 8576 KB Output is correct
6 Correct 11 ms 8576 KB Output is correct
7 Correct 11 ms 8676 KB Output is correct
8 Correct 12 ms 8576 KB Output is correct
9 Correct 11 ms 8576 KB Output is correct
10 Correct 10 ms 8576 KB Output is correct
11 Correct 13 ms 8576 KB Output is correct
12 Correct 11 ms 8576 KB Output is correct
13 Correct 11 ms 8496 KB Output is correct
14 Correct 14 ms 8448 KB Output is correct
15 Correct 10 ms 8448 KB Output is correct
16 Correct 9 ms 8320 KB Output is correct
17 Correct 15 ms 8476 KB Output is correct
18 Correct 10 ms 8448 KB Output is correct
19 Correct 11 ms 8576 KB Output is correct
20 Correct 11 ms 8448 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 47928 KB Output is correct
2 Correct 384 ms 47892 KB Output is correct
3 Correct 425 ms 48048 KB Output is correct
4 Correct 377 ms 47820 KB Output is correct
5 Correct 379 ms 47928 KB Output is correct
6 Correct 511 ms 58348 KB Output is correct
7 Correct 459 ms 53064 KB Output is correct
8 Correct 422 ms 52008 KB Output is correct
9 Correct 432 ms 50788 KB Output is correct
10 Correct 347 ms 47928 KB Output is correct
11 Correct 403 ms 48056 KB Output is correct
12 Correct 363 ms 47924 KB Output is correct
13 Correct 357 ms 48052 KB Output is correct
14 Correct 389 ms 46260 KB Output is correct
15 Correct 260 ms 40380 KB Output is correct
16 Correct 158 ms 30068 KB Output is correct
17 Correct 252 ms 41720 KB Output is correct
18 Correct 230 ms 41648 KB Output is correct
19 Correct 215 ms 42028 KB Output is correct
20 Correct 219 ms 41916 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8576 KB Output is correct
2 Correct 11 ms 8576 KB Output is correct
3 Correct 12 ms 8576 KB Output is correct
4 Correct 13 ms 8448 KB Output is correct
5 Correct 14 ms 8448 KB Output is correct
6 Correct 11 ms 8448 KB Output is correct
7 Correct 11 ms 8320 KB Output is correct
8 Correct 13 ms 8320 KB Output is correct
9 Correct 9 ms 8320 KB Output is correct
10 Correct 10 ms 8320 KB Output is correct
11 Correct 12 ms 8320 KB Output is correct
12 Correct 15 ms 8576 KB Output is correct
13 Correct 12 ms 8576 KB Output is correct
14 Correct 11 ms 8576 KB Output is correct
15 Correct 11 ms 8448 KB Output is correct
16 Correct 11 ms 8448 KB Output is correct
17 Correct 12 ms 8448 KB Output is correct
18 Correct 11 ms 8576 KB Output is correct
19 Correct 11 ms 8448 KB Output is correct
20 Correct 12 ms 8448 KB Output is correct
21 Correct 10 ms 8576 KB Output is correct
22 Correct 11 ms 8448 KB Output is correct
23 Correct 10 ms 8448 KB Output is correct
24 Correct 10 ms 8448 KB Output is correct
25 Correct 9 ms 8192 KB Output is correct
26 Correct 8 ms 8192 KB Output is correct
27 Correct 9 ms 8192 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 47840 KB Output is correct
2 Correct 404 ms 48032 KB Output is correct
3 Correct 404 ms 46492 KB Output is correct
4 Correct 349 ms 38720 KB Output is correct
5 Correct 296 ms 32208 KB Output is correct
6 Correct 237 ms 28992 KB Output is correct
7 Correct 266 ms 27720 KB Output is correct
8 Correct 260 ms 25672 KB Output is correct
9 Correct 248 ms 25064 KB Output is correct
10 Correct 283 ms 24512 KB Output is correct
11 Correct 187 ms 23220 KB Output is correct
12 Correct 190 ms 22136 KB Output is correct
13 Correct 236 ms 22156 KB Output is correct
14 Correct 187 ms 23672 KB Output is correct
15 Correct 410 ms 50604 KB Output is correct
16 Correct 411 ms 48488 KB Output is correct
17 Correct 427 ms 46412 KB Output is correct
18 Correct 423 ms 44180 KB Output is correct
19 Correct 366 ms 38716 KB Output is correct
20 Correct 351 ms 38620 KB Output is correct
21 Correct 360 ms 38648 KB Output is correct
22 Correct 281 ms 35076 KB Output is correct
23 Correct 240 ms 30660 KB Output is correct
24 Correct 323 ms 42572 KB Output is correct
25 Correct 352 ms 42552 KB Output is correct
26 Correct 292 ms 39592 KB Output is correct
27 Correct 325 ms 39348 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8192 KB Output is correct
2 Correct 9 ms 8192 KB Output is correct
3 Correct 11 ms 8192 KB Output is correct
4 Correct 11 ms 8192 KB Output is correct
5 Correct 10 ms 8192 KB Output is correct
6 Correct 10 ms 8192 KB Output is correct
7 Correct 10 ms 8192 KB Output is correct
8 Correct 12 ms 8192 KB Output is correct
9 Correct 10 ms 8192 KB Output is correct
10 Correct 9 ms 8192 KB Output is correct
11 Correct 10 ms 8192 KB Output is correct
12 Correct 8 ms 8192 KB Output is correct
13 Correct 10 ms 8192 KB Output is correct
14 Correct 8 ms 8192 KB Output is correct
15 Correct 9 ms 8192 KB Output is correct
16 Correct 9 ms 8192 KB Output is correct
17 Correct 10 ms 8192 KB Output is correct
18 Correct 10 ms 8192 KB Output is correct
19 Correct 10 ms 8192 KB Output is correct
20 Correct 10 ms 8192 KB Output is correct
21 Correct 9 ms 8192 KB Output is correct
22 Incorrect 10 ms 8192 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8192 KB Output is correct
2 Correct 9 ms 8192 KB Output is correct
3 Correct 11 ms 8192 KB Output is correct
4 Correct 11 ms 8192 KB Output is correct
5 Correct 10 ms 8192 KB Output is correct
6 Correct 10 ms 8192 KB Output is correct
7 Correct 10 ms 8192 KB Output is correct
8 Correct 12 ms 8192 KB Output is correct
9 Correct 10 ms 8192 KB Output is correct
10 Correct 9 ms 8192 KB Output is correct
11 Correct 10 ms 8192 KB Output is correct
12 Correct 8 ms 8192 KB Output is correct
13 Correct 10 ms 8192 KB Output is correct
14 Correct 8 ms 8192 KB Output is correct
15 Correct 9 ms 8192 KB Output is correct
16 Correct 9 ms 8192 KB Output is correct
17 Correct 10 ms 8192 KB Output is correct
18 Correct 10 ms 8192 KB Output is correct
19 Correct 10 ms 8192 KB Output is correct
20 Correct 10 ms 8192 KB Output is correct
21 Correct 9 ms 8192 KB Output is correct
22 Incorrect 10 ms 8192 KB Output isn't correct
23 Halted 0 ms 0 KB -