oj.uz

Submission #108752

# Submission time Handle Problem Language Result Execution time Memory
108752 2019-05-01T13:56:04 Z oolimry Duathlon (APIO18_duathlon) C++14
66 / 100
 682 ms 76716 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);
        }
        set<long long> checl;
     
        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] << " ";
                long long q = i * 1000000000ll + j;
                if(checl.find(q) != checl.end()) assert(false);
                else checl.insert(q);
            }
            //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;
            assert(sz >= 0);
            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:25: 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:25: 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:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i < biconnected.size();i++){
                       ~~^~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:133:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i < bct.size();i++){
                       ~~^~~~~~~~~~~~
count_triplets.cpp:139:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i < bct.size();i++){
                       ~~^~~~~~~~~~~~
count_triplets.cpp:141:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0;j < bct[i].adj.size();j++){
                           ~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp:151:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i < bct.size();i++){
                       ~~^~~~~~~~~~~~
count_triplets.cpp:155:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0;j < bct[i].adj.size();j++){
                           ~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp:165:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0;j < branches.size();j++) total += branches[j];
                           ~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:204:29: 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 10 ms 8192 KB Output is correct
3 Correct 9 ms 8192 KB Output is correct
4 Correct 9 ms 8192 KB Output is correct
5 Correct 9 ms 8192 KB Output is correct
6 Correct 9 ms 8192 KB Output is correct
7 Correct 8 ms 8192 KB Output is correct
8 Correct 11 ms 8192 KB Output is correct
9 Correct 11 ms 8192 KB Output is correct
10 Correct 8 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 8 ms 8192 KB Output is correct
14 Correct 12 ms 8192 KB Output is correct
15 Correct 10 ms 8192 KB Output is correct
16 Correct 10 ms 8192 KB Output is correct
17 Correct 11 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 9 ms 8192 KB Output is correct
21 Correct 8 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 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 9 ms 8192 KB Output is correct
5 Correct 9 ms 8192 KB Output is correct
6 Correct 9 ms 8192 KB Output is correct
7 Correct 8 ms 8192 KB Output is correct
8 Correct 11 ms 8192 KB Output is correct
9 Correct 11 ms 8192 KB Output is correct
10 Correct 8 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 8 ms 8192 KB Output is correct
14 Correct 12 ms 8192 KB Output is correct
15 Correct 10 ms 8192 KB Output is correct
16 Correct 10 ms 8192 KB Output is correct
17 Correct 11 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 9 ms 8192 KB Output is correct
21 Correct 8 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 224 ms 33416 KB Output is correct
2 Correct 240 ms 33480 KB Output is correct
3 Correct 435 ms 50508 KB Output is correct
4 Correct 382 ms 41924 KB Output is correct
5 Correct 449 ms 39664 KB Output is correct
6 Correct 520 ms 51128 KB Output is correct
7 Correct 481 ms 51208 KB Output is correct
8 Correct 519 ms 52616 KB Output is correct
9 Correct 474 ms 49784 KB Output is correct
10 Correct 481 ms 45844 KB Output is correct
11 Correct 356 ms 33436 KB Output is correct
12 Correct 312 ms 33852 KB Output is correct
13 Correct 221 ms 31756 KB Output is correct
14 Correct 229 ms 31296 KB Output is correct
15 Correct 212 ms 24968 KB Output is correct
16 Correct 167 ms 24644 KB Output is correct
17 Correct 10 ms 8192 KB Output is correct
18 Correct 11 ms 8212 KB Output is correct
19 Correct 14 ms 8192 KB Output is correct
20 Correct 13 ms 8320 KB Output is correct
21 Correct 12 ms 8192 KB Output is correct
22 Correct 11 ms 8192 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 57456 KB Output is correct
2 Correct 569 ms 57276 KB Output is correct
3 Correct 554 ms 57288 KB Output is correct
4 Correct 525 ms 57252 KB Output is correct
5 Correct 539 ms 57436 KB Output is correct
6 Correct 682 ms 76716 KB Output is correct
7 Correct 656 ms 68396 KB Output is correct
8 Correct 540 ms 65964 KB Output is correct
9 Correct 529 ms 63932 KB Output is correct
10 Correct 535 ms 57292 KB Output is correct
11 Correct 501 ms 57264 KB Output is correct
12 Correct 522 ms 57380 KB Output is correct
13 Correct 565 ms 57400 KB Output is correct
14 Correct 421 ms 52268 KB Output is correct
15 Correct 453 ms 46904 KB Output is correct
16 Correct 222 ms 29900 KB Output is correct
17 Correct 467 ms 49876 KB Output is correct
18 Correct 288 ms 48176 KB Output is correct
19 Correct 277 ms 48304 KB Output is correct
20 Correct 287 ms 47760 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 14 ms 8632 KB Output is correct
3 Correct 15 ms 8576 KB Output is correct
4 Correct 16 ms 8576 KB Output is correct
5 Correct 14 ms 8524 KB Output is correct
6 Correct 12 ms 8320 KB Output is correct
7 Correct 11 ms 8320 KB Output is correct
8 Correct 11 ms 8320 KB Output is correct
9 Correct 10 ms 8320 KB Output is correct
10 Correct 14 ms 8320 KB Output is correct
11 Correct 10 ms 8320 KB Output is correct
12 Correct 12 ms 8704 KB Output is correct
13 Correct 12 ms 8704 KB Output is correct
14 Correct 11 ms 8704 KB Output is correct
15 Correct 15 ms 8576 KB Output is correct
16 Correct 12 ms 8576 KB Output is correct
17 Correct 12 ms 8576 KB Output is correct
18 Correct 11 ms 8448 KB Output is correct
19 Correct 16 ms 8420 KB Output is correct
20 Correct 10 ms 8320 KB Output is correct
21 Correct 11 ms 8576 KB Output is correct
22 Correct 12 ms 8576 KB Output is correct
23 Correct 12 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 9 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 571 ms 57336 KB Output is correct
2 Correct 568 ms 59940 KB Output is correct
3 Correct 646 ms 54636 KB Output is correct
4 Correct 507 ms 44416 KB Output is correct
5 Correct 364 ms 33564 KB Output is correct
6 Correct 309 ms 28996 KB Output is correct
7 Correct 308 ms 26428 KB Output is correct
8 Correct 234 ms 23244 KB Output is correct
9 Correct 258 ms 22092 KB Output is correct
10 Correct 240 ms 21072 KB Output is correct
11 Correct 196 ms 19212 KB Output is correct
12 Correct 227 ms 18040 KB Output is correct
13 Correct 225 ms 18004 KB Output is correct
14 Correct 211 ms 21372 KB Output is correct
15 Correct 666 ms 63660 KB Output is correct
16 Correct 574 ms 59848 KB Output is correct
17 Correct 595 ms 57012 KB Output is correct
18 Correct 515 ms 53944 KB Output is correct
19 Correct 468 ms 44532 KB Output is correct
20 Correct 529 ms 44412 KB Output is correct
21 Correct 433 ms 44348 KB Output is correct
22 Correct 355 ms 38076 KB Output is correct
23 Correct 299 ms 30472 KB Output is correct
24 Correct 395 ms 50044 KB Output is correct
25 Correct 400 ms 50132 KB Output is correct
26 Correct 418 ms 45880 KB Output is correct
27 Correct 479 ms 45108 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 9 ms 8192 KB Output is correct
5 Correct 9 ms 8192 KB Output is correct
6 Correct 9 ms 8192 KB Output is correct
7 Correct 8 ms 8192 KB Output is correct
8 Correct 11 ms 8192 KB Output is correct
9 Correct 11 ms 8192 KB Output is correct
10 Correct 8 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 8 ms 8192 KB Output is correct
14 Correct 12 ms 8192 KB Output is correct
15 Correct 10 ms 8192 KB Output is correct
16 Correct 10 ms 8192 KB Output is correct
17 Correct 11 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 9 ms 8192 KB Output is correct
21 Correct 8 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 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 9 ms 8192 KB Output is correct
5 Correct 9 ms 8192 KB Output is correct
6 Correct 9 ms 8192 KB Output is correct
7 Correct 8 ms 8192 KB Output is correct
8 Correct 11 ms 8192 KB Output is correct
9 Correct 11 ms 8192 KB Output is correct
10 Correct 8 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 8 ms 8192 KB Output is correct
14 Correct 12 ms 8192 KB Output is correct
15 Correct 10 ms 8192 KB Output is correct
16 Correct 10 ms 8192 KB Output is correct
17 Correct 11 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 9 ms 8192 KB Output is correct
21 Correct 8 ms 8192 KB Output is correct
22 Incorrect 10 ms 8192 KB Output isn't correct
23 Halted 0 ms 0 KB -