oj.uz

Submission #108716

# Submission time Handle Problem Language Result Execution time Memory
108716 2019-05-01T06:58:16 Z oolimry Duathlon (APIO18_duathlon) C++14
66 / 100
 525 ms 57140 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 r;
    int p = -1;
    vi adj;
};

vector<node2> bct; ///block-cut tree
long long root = -1;
void dp(int u){
    if(bct[u].vis) return;
    bct[u].vis = true;
    bct[u].dp = bct[u].sz;
    bct[u].r = root;
    for(int i = 0;i < bct[u].adj.size();i++){
        int v = bct[u].adj[i];
        if(bct[v].vis) continue;
        bct[v].p = u;
        dp(v);
        bct[u].dp += 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);
        }
    }


    for(int i = 0;i < biconnected.size();i++){
        node2 nn;
        nn.sz = biconnected[i].size();
        nn.isArti = false;
        for(unordered_set<int>::iterator it = biconnected[i].begin();it != biconnected[i].end();it++){
            //cout << *it << " ";
            if(artis.find(*it) != artis.end()){
                nn.adj.push_back(artis[*it]);
                bct[artis[*it]].adj.push_back(bct.size());
                nn.sz--;
            }
        }
        bct.push_back(nn);
        //cout << "\n";
    }
    for(int i = 0;i < bct.size();i++){
        root = i;
        dp(i);
    }
    /*
    for(int i = 0;i < bct.size();i++){
        cout << i << " " << bct[i].sz << " " << bct[i].dp << " " << bct[i].isArti << "| ";
        for(int j = 0;j < bct[i].adj.size();j++){
            cout << bct[i].adj[j] << " ";
        }
        cout << "\n";
    }
    */
    long long ans = 0ll;
    for(int i = 0;i < bct.size();i++){
        vector<long long> branches;
        vector<long long> branchStart;
        long long total = 0ll;
        for(int j = 0;j < bct[i].adj.size();j++){
            if(bct[i].adj[j] != bct[i].p){
                branches.push_back(bct[bct[i].adj[j]].dp);
                branchStart.push_back(bct[bct[i].adj[j]].sz);
            }
        }
        if(bct[i].p >= 0){
            branches.push_back(bct[bct[i].r].dp - bct[i].dp);
            branchStart.push_back(bct[bct[i].p].sz);
        }
        for(int j = 0;j < branches.size();j++) total += branches[j];
        /*
        long long extra = 0, extra2 = 0;
        if(!bct[i].isArti) extra = max(0ll,(long long)(bct[i].adj.size())-2);
        if(!bct[i].isArti) extra2 = max(0ll,(long long)(bct[i].adj.size())-1);
        for(int j = 0;j < branches.size();j++){
            //cout << i << " " << branches[j] << "\n";
            ///branch1 to self or neighbor articulation point to branch2
            ans += branches[j] * (total - branches[j]) * (bct[i].sz + extra);

            ///branch to self to self or self to self to branch
            ans += 2 * (bct[i].sz) * (bct[i].sz + extra2 - 1) * branches[j];

            ///self to arti to another branch
            //if(!bct[i].isArti){
            //    ans += 2ll * (bct[i].sz) * branches[j] * (bct[i].adj.size() - 1);
            //}

            if(bct[i].isArti){
                ///direct branch to self to same branch(not reverse) or its reverse
                ans += 2ll * bct[i].sz * branchStart[j] * (branches[j] - branchStart[j]);
                ///direct branch to self to direct or its reverse
                ans += bct[i].sz * (branchStart[j]) * (branchStart[j] - 1);

            }
        }


        ///self to self to self
        ans += (bct[i].sz) * (bct[i].sz - 1) * (bct[i].sz - 2);
        */

        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 = 0;
                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 'void dp(int)':
count_triplets.cpp:74:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < bct[u].adj.size();i++){
                   ~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:118:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < biconnected.size();i++){
                   ~~^~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:133:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < bct.size();i++){
                   ~~^~~~~~~~~~~~
count_triplets.cpp:147:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < bct.size();i++){
                   ~~^~~~~~~~~~~~
count_triplets.cpp:151:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < bct[i].adj.size();j++){
                       ~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp:161:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < branches.size();j++) total += branches[j];
                       ~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:199:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < bct[i].adj.size();j++){
                       ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8192 KB Output is correct
2 Correct 12 ms 8108 KB Output is correct
3 Correct 12 ms 8192 KB Output is correct
4 Correct 10 ms 8192 KB Output is correct
5 Correct 10 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 11 ms 8192 KB Output is correct
9 Correct 9 ms 8192 KB Output is correct
10 Correct 11 ms 8192 KB Output is correct
11 Correct 12 ms 8140 KB Output is correct
12 Correct 11 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 9 ms 8192 KB Output is correct
16 Correct 11 ms 8192 KB Output is correct
17 Correct 12 ms 8192 KB Output is correct
18 Correct 11 ms 8192 KB Output is correct
19 Correct 9 ms 8192 KB Output is correct
20 Correct 11 ms 8192 KB Output is correct
21 Correct 12 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 12 ms 8108 KB Output is correct
3 Correct 12 ms 8192 KB Output is correct
4 Correct 10 ms 8192 KB Output is correct
5 Correct 10 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 11 ms 8192 KB Output is correct
9 Correct 9 ms 8192 KB Output is correct
10 Correct 11 ms 8192 KB Output is correct
11 Correct 12 ms 8140 KB Output is correct
12 Correct 11 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 9 ms 8192 KB Output is correct
16 Correct 11 ms 8192 KB Output is correct
17 Correct 12 ms 8192 KB Output is correct
18 Correct 11 ms 8192 KB Output is correct
19 Correct 9 ms 8192 KB Output is correct
20 Correct 11 ms 8192 KB Output is correct
21 Correct 12 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 219 ms 32380 KB Output is correct
2 Correct 239 ms 32364 KB Output is correct
3 Correct 349 ms 40156 KB Output is correct
4 Correct 269 ms 36340 KB Output is correct
5 Correct 320 ms 36084 KB Output is correct
6 Correct 385 ms 39652 KB Output is correct
7 Correct 381 ms 39028 KB Output is correct
8 Correct 395 ms 40312 KB Output is correct
9 Correct 370 ms 37448 KB Output is correct
10 Correct 359 ms 35520 KB Output is correct
11 Correct 240 ms 31444 KB Output is correct
12 Correct 243 ms 31080 KB Output is correct
13 Correct 198 ms 30788 KB Output is correct
14 Correct 187 ms 30400 KB Output is correct
15 Correct 134 ms 24272 KB Output is correct
16 Correct 167 ms 23904 KB Output is correct
17 Correct 10 ms 8192 KB Output is correct
18 Correct 11 ms 8192 KB Output is correct
19 Correct 12 ms 8192 KB Output is correct
20 Correct 13 ms 8192 KB Output is correct
21 Correct 11 ms 8192 KB Output is correct
22 Correct 10 ms 8192 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 48744 KB Output is correct
2 Correct 493 ms 48792 KB Output is correct
3 Correct 399 ms 48668 KB Output is correct
4 Correct 415 ms 48624 KB Output is correct
5 Correct 397 ms 48748 KB Output is correct
6 Correct 494 ms 57140 KB Output is correct
7 Correct 525 ms 54240 KB Output is correct
8 Correct 448 ms 52776 KB Output is correct
9 Correct 423 ms 51420 KB Output is correct
10 Correct 432 ms 48696 KB Output is correct
11 Correct 398 ms 48640 KB Output is correct
12 Correct 394 ms 48680 KB Output is correct
13 Correct 398 ms 48696 KB Output is correct
14 Correct 439 ms 47144 KB Output is correct
15 Correct 463 ms 37688 KB Output is correct
16 Correct 185 ms 29252 KB Output is correct
17 Correct 238 ms 40472 KB Output is correct
18 Correct 198 ms 40244 KB Output is correct
19 Correct 206 ms 40364 KB Output is correct
20 Correct 206 ms 40124 KB Output is correct

Subtask #6
15.0 / 15.0

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

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 48648 KB Output is correct
2 Correct 399 ms 48564 KB Output is correct
3 Correct 410 ms 47284 KB Output is correct
4 Correct 432 ms 33856 KB Output is correct
5 Correct 311 ms 27484 KB Output is correct
6 Correct 243 ms 24524 KB Output is correct
7 Correct 220 ms 23996 KB Output is correct
8 Correct 211 ms 20652 KB Output is correct
9 Correct 201 ms 20304 KB Output is correct
10 Correct 201 ms 19024 KB Output is correct
11 Correct 196 ms 17912 KB Output is correct
12 Correct 182 ms 17400 KB Output is correct
13 Correct 183 ms 17344 KB Output is correct
14 Correct 195 ms 20728 KB Output is correct
15 Correct 448 ms 53736 KB Output is correct
16 Correct 452 ms 51508 KB Output is correct
17 Correct 404 ms 44600 KB Output is correct
18 Correct 426 ms 42296 KB Output is correct
19 Correct 357 ms 33864 KB Output is correct
20 Correct 349 ms 34108 KB Output is correct
21 Correct 332 ms 33944 KB Output is correct
22 Correct 284 ms 32416 KB Output is correct
23 Correct 271 ms 26916 KB Output is correct
24 Correct 346 ms 39592 KB Output is correct
25 Correct 311 ms 39552 KB Output is correct
26 Correct 331 ms 37400 KB Output is correct
27 Correct 315 ms 37144 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 12 ms 8108 KB Output is correct
3 Correct 12 ms 8192 KB Output is correct
4 Correct 10 ms 8192 KB Output is correct
5 Correct 10 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 11 ms 8192 KB Output is correct
9 Correct 9 ms 8192 KB Output is correct
10 Correct 11 ms 8192 KB Output is correct
11 Correct 12 ms 8140 KB Output is correct
12 Correct 11 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 9 ms 8192 KB Output is correct
16 Correct 11 ms 8192 KB Output is correct
17 Correct 12 ms 8192 KB Output is correct
18 Correct 11 ms 8192 KB Output is correct
19 Correct 9 ms 8192 KB Output is correct
20 Correct 11 ms 8192 KB Output is correct
21 Correct 12 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 12 ms 8108 KB Output is correct
3 Correct 12 ms 8192 KB Output is correct
4 Correct 10 ms 8192 KB Output is correct
5 Correct 10 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 11 ms 8192 KB Output is correct
9 Correct 9 ms 8192 KB Output is correct
10 Correct 11 ms 8192 KB Output is correct
11 Correct 12 ms 8140 KB Output is correct
12 Correct 11 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 9 ms 8192 KB Output is correct
16 Correct 11 ms 8192 KB Output is correct
17 Correct 12 ms 8192 KB Output is correct
18 Correct 11 ms 8192 KB Output is correct
19 Correct 9 ms 8192 KB Output is correct
20 Correct 11 ms 8192 KB Output is correct
21 Correct 12 ms 8192 KB Output is correct
22 Incorrect 9 ms 8192 KB Output isn't correct
23 Halted 0 ms 0 KB -