oj.uz

Submission #108871

# Submission time Handle Problem Language Result Execution time Memory
108871 2019-05-02T10:44:36 Z oolimry Duathlon (APIO18_duathlon) C++14
66 / 100
 526 ms 58676 KB 
#include <bits/stdc++.h>

using namespace std;
int n, m;
typedef vector<int> vi;
typedef pair<int,int> ii;
struct node{
    int depth = -1;
    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;
void dfs(int u){
    if(g[u].depth == -1) g[u].depth = g[g[u].parent].depth + 1;
    g[u].low = g[u].depth;
    g[u].vis = true;
    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(g[u].depth == 0) 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].depth){
                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{
                    assert(!s.empty());
                    nn = s.top();
                    s.pop();
                    biconnected.back().insert(nn);
                }while(nn != u);
            }
            ///if(g[v].low > g[u].depth{
                  ///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;
            g[i].depth = 0;
            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(g[i].isArti){
            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:25: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:70: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:86: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:133:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < biconnected.size();i++){
                   ~~^~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:145:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0;j < components[i].size();j++){
                           ~~^~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:157: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 9 ms 8192 KB Output is correct
2 Correct 9 ms 8192 KB Output is correct
3 Correct 10 ms 8192 KB Output is correct
4 Correct 11 ms 8192 KB Output is correct
5 Correct 11 ms 8192 KB Output is correct
6 Correct 11 ms 8192 KB Output is correct
7 Correct 12 ms 8192 KB Output is correct
8 Correct 6 ms 8192 KB Output is correct
9 Correct 10 ms 8192 KB Output is correct
10 Correct 11 ms 8192 KB Output is correct
11 Correct 10 ms 8192 KB Output is correct
12 Correct 10 ms 8192 KB Output is correct
13 Correct 10 ms 8192 KB Output is correct
14 Correct 10 ms 8192 KB Output is correct
15 Correct 8 ms 8192 KB Output is correct
16 Correct 9 ms 8192 KB Output is correct
17 Correct 9 ms 8192 KB Output is correct
18 Correct 10 ms 8192 KB Output is correct
19 Correct 11 ms 8192 KB Output is correct
20 Correct 9 ms 8192 KB Output is correct
21 Correct 9 ms 8192 KB Output is correct
22 Incorrect 9 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 9 ms 8192 KB Output is correct
2 Correct 9 ms 8192 KB Output is correct
3 Correct 10 ms 8192 KB Output is correct
4 Correct 11 ms 8192 KB Output is correct
5 Correct 11 ms 8192 KB Output is correct
6 Correct 11 ms 8192 KB Output is correct
7 Correct 12 ms 8192 KB Output is correct
8 Correct 6 ms 8192 KB Output is correct
9 Correct 10 ms 8192 KB Output is correct
10 Correct 11 ms 8192 KB Output is correct
11 Correct 10 ms 8192 KB Output is correct
12 Correct 10 ms 8192 KB Output is correct
13 Correct 10 ms 8192 KB Output is correct
14 Correct 10 ms 8192 KB Output is correct
15 Correct 8 ms 8192 KB Output is correct
16 Correct 9 ms 8192 KB Output is correct
17 Correct 9 ms 8192 KB Output is correct
18 Correct 10 ms 8192 KB Output is correct
19 Correct 11 ms 8192 KB Output is correct
20 Correct 9 ms 8192 KB Output is correct
21 Correct 9 ms 8192 KB Output is correct
22 Incorrect 9 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 202 ms 34948 KB Output is correct
2 Correct 257 ms 34996 KB Output is correct
3 Correct 380 ms 42484 KB Output is correct
4 Correct 300 ms 39080 KB Output is correct
5 Correct 308 ms 36212 KB Output is correct
6 Correct 399 ms 42588 KB Output is correct
7 Correct 421 ms 42428 KB Output is correct
8 Correct 438 ms 42752 KB Output is correct
9 Correct 410 ms 41548 KB Output is correct
10 Correct 380 ms 38736 KB Output is correct
11 Correct 213 ms 33012 KB Output is correct
12 Correct 254 ms 32832 KB Output is correct
13 Correct 251 ms 32592 KB Output is correct
14 Correct 277 ms 32064 KB Output is correct
15 Correct 183 ms 26700 KB Output is correct
16 Correct 171 ms 26440 KB Output is correct
17 Correct 17 ms 10624 KB Output is correct
18 Correct 14 ms 10624 KB Output is correct
19 Correct 12 ms 10496 KB Output is correct
20 Correct 13 ms 10624 KB Output is correct
21 Correct 14 ms 10496 KB Output is correct
22 Correct 13 ms 10496 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8576 KB Output is correct
2 Correct 12 ms 8576 KB Output is correct
3 Correct 12 ms 8496 KB Output is correct
4 Correct 13 ms 8704 KB Output is correct
5 Correct 13 ms 8576 KB Output is correct
6 Correct 11 ms 8576 KB Output is correct
7 Correct 11 ms 8696 KB Output is correct
8 Correct 12 ms 8576 KB Output is correct
9 Correct 12 ms 8704 KB Output is correct
10 Correct 14 ms 8576 KB Output is correct
11 Correct 11 ms 8576 KB Output is correct
12 Correct 12 ms 8704 KB Output is correct
13 Correct 11 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 9 ms 8320 KB Output is correct
17 Correct 10 ms 8448 KB Output is correct
18 Correct 10 ms 8448 KB Output is correct
19 Correct 10 ms 8476 KB Output is correct
20 Correct 10 ms 8448 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 47920 KB Output is correct
2 Correct 368 ms 48104 KB Output is correct
3 Correct 362 ms 48096 KB Output is correct
4 Correct 385 ms 48308 KB Output is correct
5 Correct 372 ms 48184 KB Output is correct
6 Correct 498 ms 58676 KB Output is correct
7 Correct 464 ms 53036 KB Output is correct
8 Correct 482 ms 52420 KB Output is correct
9 Correct 472 ms 50964 KB Output is correct
10 Correct 426 ms 48336 KB Output is correct
11 Correct 394 ms 48328 KB Output is correct
12 Correct 391 ms 48284 KB Output is correct
13 Correct 385 ms 48056 KB Output is correct
14 Correct 322 ms 46392 KB Output is correct
15 Correct 289 ms 40560 KB Output is correct
16 Correct 173 ms 30148 KB Output is correct
17 Correct 244 ms 41932 KB Output is correct
18 Correct 248 ms 41776 KB Output is correct
19 Correct 232 ms 42252 KB Output is correct
20 Correct 244 ms 42040 KB Output is correct

Subtask #6
15.0 / 15.0

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

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 47980 KB Output is correct
2 Correct 401 ms 48288 KB Output is correct
3 Correct 418 ms 46704 KB Output is correct
4 Correct 388 ms 38860 KB Output is correct
5 Correct 311 ms 32224 KB Output is correct
6 Correct 306 ms 29196 KB Output is correct
7 Correct 309 ms 27672 KB Output is correct
8 Correct 227 ms 25804 KB Output is correct
9 Correct 243 ms 24980 KB Output is correct
10 Correct 251 ms 24580 KB Output is correct
11 Correct 228 ms 23348 KB Output is correct
12 Correct 235 ms 22456 KB Output is correct
13 Correct 196 ms 22220 KB Output is correct
14 Correct 275 ms 23952 KB Output is correct
15 Correct 526 ms 50744 KB Output is correct
16 Correct 410 ms 48564 KB Output is correct
17 Correct 464 ms 46496 KB Output is correct
18 Correct 394 ms 44368 KB Output is correct
19 Correct 362 ms 38680 KB Output is correct
20 Correct 398 ms 38772 KB Output is correct
21 Correct 391 ms 38776 KB Output is correct
22 Correct 301 ms 35272 KB Output is correct
23 Correct 244 ms 30932 KB Output is correct
24 Correct 317 ms 42556 KB Output is correct
25 Correct 385 ms 42984 KB Output is correct
26 Correct 318 ms 39572 KB Output is correct
27 Correct 375 ms 39624 KB Output is correct

Subtask #8
0 / 8.0

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