oj.uz

Submission #108875

# Submission time Handle Problem Language Result Execution time Memory
108875 2019-05-02T10:50:33 Z oolimry Duathlon (APIO18_duathlon) C++14
66 / 100
 544 ms 58380 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(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: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 9 ms 8192 KB Output is correct
2 Correct 10 ms 8192 KB Output is correct
3 Correct 9 ms 8192 KB Output is correct
4 Correct 10 ms 8192 KB Output is correct
5 Correct 9 ms 8192 KB Output is correct
6 Correct 11 ms 8192 KB Output is correct
7 Correct 11 ms 8192 KB Output is correct
8 Correct 9 ms 8192 KB Output is correct
9 Correct 9 ms 8192 KB Output is correct
10 Correct 9 ms 8192 KB Output is correct
11 Correct 10 ms 8320 KB Output is correct
12 Correct 9 ms 8192 KB Output is correct
13 Correct 8 ms 8192 KB Output is correct
14 Correct 9 ms 8192 KB Output is correct
15 Correct 8 ms 8192 KB Output is correct
16 Correct 10 ms 8192 KB Output is correct
17 Correct 8 ms 8192 KB Output is correct
18 Correct 11 ms 8192 KB Output is correct
19 Correct 8 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 8 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 10 ms 8192 KB Output is correct
3 Correct 9 ms 8192 KB Output is correct
4 Correct 10 ms 8192 KB Output is correct
5 Correct 9 ms 8192 KB Output is correct
6 Correct 11 ms 8192 KB Output is correct
7 Correct 11 ms 8192 KB Output is correct
8 Correct 9 ms 8192 KB Output is correct
9 Correct 9 ms 8192 KB Output is correct
10 Correct 9 ms 8192 KB Output is correct
11 Correct 10 ms 8320 KB Output is correct
12 Correct 9 ms 8192 KB Output is correct
13 Correct 8 ms 8192 KB Output is correct
14 Correct 9 ms 8192 KB Output is correct
15 Correct 8 ms 8192 KB Output is correct
16 Correct 10 ms 8192 KB Output is correct
17 Correct 8 ms 8192 KB Output is correct
18 Correct 11 ms 8192 KB Output is correct
19 Correct 8 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 8 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 209 ms 34944 KB Output is correct
2 Correct 212 ms 34876 KB Output is correct
3 Correct 347 ms 42484 KB Output is correct
4 Correct 287 ms 38964 KB Output is correct
5 Correct 298 ms 35960 KB Output is correct
6 Correct 391 ms 42204 KB Output is correct
7 Correct 378 ms 42036 KB Output is correct
8 Correct 407 ms 42564 KB Output is correct
9 Correct 390 ms 41404 KB Output is correct
10 Correct 346 ms 38512 KB Output is correct
11 Correct 243 ms 32704 KB Output is correct
12 Correct 267 ms 32564 KB Output is correct
13 Correct 204 ms 32200 KB Output is correct
14 Correct 191 ms 31808 KB Output is correct
15 Correct 150 ms 26280 KB Output is correct
16 Correct 160 ms 26008 KB Output is correct
17 Correct 12 ms 10496 KB Output is correct
18 Correct 13 ms 10624 KB Output is correct
19 Correct 16 ms 10496 KB Output is correct
20 Correct 17 ms 10624 KB Output is correct
21 Correct 13 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 8548 KB Output is correct
2 Correct 11 ms 8576 KB Output is correct
3 Correct 12 ms 8576 KB Output is correct
4 Correct 11 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 8576 KB Output is correct
8 Correct 10 ms 8576 KB Output is correct
9 Correct 11 ms 8704 KB Output is correct
10 Correct 10 ms 8576 KB Output is correct
11 Correct 11 ms 8576 KB Output is correct
12 Correct 10 ms 8576 KB Output is correct
13 Correct 11 ms 8576 KB Output is correct
14 Correct 11 ms 8448 KB Output is correct
15 Correct 11 ms 8448 KB Output is correct
16 Correct 13 ms 8448 KB Output is correct
17 Correct 10 ms 8448 KB Output is correct
18 Correct 11 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 394 ms 47836 KB Output is correct
2 Correct 371 ms 48056 KB Output is correct
3 Correct 372 ms 47924 KB Output is correct
4 Correct 371 ms 48052 KB Output is correct
5 Correct 367 ms 47796 KB Output is correct
6 Correct 513 ms 58380 KB Output is correct
7 Correct 487 ms 52860 KB Output is correct
8 Correct 450 ms 52092 KB Output is correct
9 Correct 398 ms 50684 KB Output is correct
10 Correct 408 ms 48028 KB Output is correct
11 Correct 391 ms 47996 KB Output is correct
12 Correct 402 ms 48052 KB Output is correct
13 Correct 390 ms 48064 KB Output is correct
14 Correct 333 ms 46436 KB Output is correct
15 Correct 331 ms 40480 KB Output is correct
16 Correct 177 ms 30200 KB Output is correct
17 Correct 246 ms 41840 KB Output is correct
18 Correct 278 ms 41712 KB Output is correct
19 Correct 279 ms 42152 KB Output is correct
20 Correct 250 ms 42024 KB Output is correct

Subtask #6
15.0 / 15.0

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

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 47920 KB Output is correct
2 Correct 476 ms 48040 KB Output is correct
3 Correct 407 ms 46580 KB Output is correct
4 Correct 357 ms 38708 KB Output is correct
5 Correct 274 ms 32196 KB Output is correct
6 Correct 263 ms 29128 KB Output is correct
7 Correct 256 ms 27716 KB Output is correct
8 Correct 269 ms 25800 KB Output is correct
9 Correct 294 ms 24908 KB Output is correct
10 Correct 237 ms 24584 KB Output is correct
11 Correct 191 ms 23348 KB Output is correct
12 Correct 200 ms 22264 KB Output is correct
13 Correct 192 ms 22264 KB Output is correct
14 Correct 206 ms 23916 KB Output is correct
15 Correct 474 ms 50672 KB Output is correct
16 Correct 544 ms 48548 KB Output is correct
17 Correct 464 ms 46644 KB Output is correct
18 Correct 449 ms 44216 KB Output is correct
19 Correct 417 ms 38888 KB Output is correct
20 Correct 389 ms 38708 KB Output is correct
21 Correct 361 ms 38692 KB Output is correct
22 Correct 317 ms 35252 KB Output is correct
23 Correct 269 ms 30784 KB Output is correct
24 Correct 321 ms 42552 KB Output is correct
25 Correct 384 ms 42816 KB Output is correct
26 Correct 357 ms 39732 KB Output is correct
27 Correct 343 ms 39604 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 10 ms 8192 KB Output is correct
3 Correct 9 ms 8192 KB Output is correct
4 Correct 10 ms 8192 KB Output is correct
5 Correct 9 ms 8192 KB Output is correct
6 Correct 11 ms 8192 KB Output is correct
7 Correct 11 ms 8192 KB Output is correct
8 Correct 9 ms 8192 KB Output is correct
9 Correct 9 ms 8192 KB Output is correct
10 Correct 9 ms 8192 KB Output is correct
11 Correct 10 ms 8320 KB Output is correct
12 Correct 9 ms 8192 KB Output is correct
13 Correct 8 ms 8192 KB Output is correct
14 Correct 9 ms 8192 KB Output is correct
15 Correct 8 ms 8192 KB Output is correct
16 Correct 10 ms 8192 KB Output is correct
17 Correct 8 ms 8192 KB Output is correct
18 Correct 11 ms 8192 KB Output is correct
19 Correct 8 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 8 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 10 ms 8192 KB Output is correct
3 Correct 9 ms 8192 KB Output is correct
4 Correct 10 ms 8192 KB Output is correct
5 Correct 9 ms 8192 KB Output is correct
6 Correct 11 ms 8192 KB Output is correct
7 Correct 11 ms 8192 KB Output is correct
8 Correct 9 ms 8192 KB Output is correct
9 Correct 9 ms 8192 KB Output is correct
10 Correct 9 ms 8192 KB Output is correct
11 Correct 10 ms 8320 KB Output is correct
12 Correct 9 ms 8192 KB Output is correct
13 Correct 8 ms 8192 KB Output is correct
14 Correct 9 ms 8192 KB Output is correct
15 Correct 8 ms 8192 KB Output is correct
16 Correct 10 ms 8192 KB Output is correct
17 Correct 8 ms 8192 KB Output is correct
18 Correct 11 ms 8192 KB Output is correct
19 Correct 8 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 8 ms 8192 KB Output isn't correct
23 Halted 0 ms 0 KB -