oj.uz

Submission #108718

# Submission time Handle Problem Language Result Execution time Memory
108718 2019-05-01T07:12:10 Z oolimry Duathlon (APIO18_duathlon) C++14
66 / 100
 719 ms 75700 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;
        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:139:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < bct.size();i++){
                   ~~^~~~~~~~~~~~
count_triplets.cpp:141:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < bct[i].adj.size();j++){
                       ~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp:151:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < bct.size();i++){
                   ~~^~~~~~~~~~~~
count_triplets.cpp:155:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < bct[i].adj.size();j++){
                       ~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp:165: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:203: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 11 ms 8192 KB Output is correct
2 Correct 8 ms 8192 KB Output is correct
3 Correct 10 ms 8236 KB Output is correct
4 Correct 11 ms 8192 KB Output is correct
5 Correct 9 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 11 ms 8192 KB Output is correct
9 Correct 10 ms 8192 KB Output is correct
10 Correct 10 ms 8192 KB Output is correct
11 Correct 9 ms 8192 KB Output is correct
12 Correct 10 ms 8192 KB Output is correct
13 Correct 9 ms 8192 KB Output is correct
14 Correct 10 ms 8192 KB Output is correct
15 Correct 11 ms 8192 KB Output is correct
16 Correct 10 ms 8064 KB Output is correct
17 Correct 10 ms 8192 KB Output is correct
18 Correct 11 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 10 ms 8192 KB Output is correct
22 Incorrect 11 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 11 ms 8192 KB Output is correct
2 Correct 8 ms 8192 KB Output is correct
3 Correct 10 ms 8236 KB Output is correct
4 Correct 11 ms 8192 KB Output is correct
5 Correct 9 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 11 ms 8192 KB Output is correct
9 Correct 10 ms 8192 KB Output is correct
10 Correct 10 ms 8192 KB Output is correct
11 Correct 9 ms 8192 KB Output is correct
12 Correct 10 ms 8192 KB Output is correct
13 Correct 9 ms 8192 KB Output is correct
14 Correct 10 ms 8192 KB Output is correct
15 Correct 11 ms 8192 KB Output is correct
16 Correct 10 ms 8064 KB Output is correct
17 Correct 10 ms 8192 KB Output is correct
18 Correct 11 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 10 ms 8192 KB Output is correct
22 Incorrect 11 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 208 ms 32364 KB Output is correct
2 Correct 229 ms 32308 KB Output is correct
3 Correct 431 ms 49516 KB Output is correct
4 Correct 344 ms 40776 KB Output is correct
5 Correct 351 ms 38812 KB Output is correct
6 Correct 499 ms 50160 KB Output is correct
7 Correct 494 ms 50288 KB Output is correct
8 Correct 431 ms 51644 KB Output is correct
9 Correct 454 ms 48704 KB Output is correct
10 Correct 393 ms 44772 KB Output is correct
11 Correct 336 ms 32568 KB Output is correct
12 Correct 288 ms 32928 KB Output is correct
13 Correct 266 ms 30812 KB Output is correct
14 Correct 240 ms 30408 KB Output is correct
15 Correct 177 ms 24196 KB Output is correct
16 Correct 202 ms 23924 KB Output is correct
17 Correct 13 ms 8192 KB Output is correct
18 Correct 10 ms 8192 KB Output is correct
19 Correct 13 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 13 ms 8192 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 11 ms 8704 KB Output is correct
3 Correct 12 ms 8704 KB Output is correct
4 Correct 12 ms 8832 KB Output is correct
5 Correct 12 ms 8696 KB Output is correct
6 Correct 12 ms 8704 KB Output is correct
7 Correct 13 ms 8832 KB Output is correct
8 Correct 11 ms 8704 KB Output is correct
9 Correct 12 ms 8704 KB Output is correct
10 Correct 12 ms 8704 KB Output is correct
11 Correct 13 ms 8704 KB Output is correct
12 Correct 12 ms 8704 KB Output is correct
13 Correct 13 ms 8732 KB Output is correct
14 Correct 14 ms 8576 KB Output is correct
15 Correct 11 ms 8448 KB Output is correct
16 Correct 14 ms 8444 KB Output is correct
17 Correct 12 ms 8576 KB Output is correct
18 Correct 11 ms 8576 KB Output is correct
19 Correct 11 ms 8576 KB Output is correct
20 Correct 32 ms 8576 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 56236 KB Output is correct
2 Correct 513 ms 56304 KB Output is correct
3 Correct 509 ms 56268 KB Output is correct
4 Correct 534 ms 56188 KB Output is correct
5 Correct 512 ms 56228 KB Output is correct
6 Correct 719 ms 75700 KB Output is correct
7 Correct 585 ms 67372 KB Output is correct
8 Correct 592 ms 65028 KB Output is correct
9 Correct 622 ms 63164 KB Output is correct
10 Correct 564 ms 56184 KB Output is correct
11 Correct 546 ms 56236 KB Output is correct
12 Correct 536 ms 56236 KB Output is correct
13 Correct 549 ms 56216 KB Output is correct
14 Correct 512 ms 51444 KB Output is correct
15 Correct 449 ms 46028 KB Output is correct
16 Correct 208 ms 29376 KB Output is correct
17 Correct 308 ms 48920 KB Output is correct
18 Correct 318 ms 47156 KB Output is correct
19 Correct 393 ms 47288 KB Output is correct
20 Correct 318 ms 46652 KB Output is correct

Subtask #6
15.0 / 15.0

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

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 56240 KB Output is correct
2 Correct 576 ms 58972 KB Output is correct
3 Correct 539 ms 53420 KB Output is correct
4 Correct 410 ms 43708 KB Output is correct
5 Correct 313 ms 33212 KB Output is correct
6 Correct 281 ms 28100 KB Output is correct
7 Correct 233 ms 25668 KB Output is correct
8 Correct 212 ms 22732 KB Output is correct
9 Correct 224 ms 21452 KB Output is correct
10 Correct 234 ms 20424 KB Output is correct
11 Correct 191 ms 18672 KB Output is correct
12 Correct 210 ms 17424 KB Output is correct
13 Correct 206 ms 17444 KB Output is correct
14 Correct 188 ms 20728 KB Output is correct
15 Correct 531 ms 62608 KB Output is correct
16 Correct 554 ms 59180 KB Output is correct
17 Correct 529 ms 56268 KB Output is correct
18 Correct 507 ms 53176 KB Output is correct
19 Correct 448 ms 43704 KB Output is correct
20 Correct 427 ms 43752 KB Output is correct
21 Correct 495 ms 43836 KB Output is correct
22 Correct 378 ms 37428 KB Output is correct
23 Correct 301 ms 29760 KB Output is correct
24 Correct 451 ms 49564 KB Output is correct
25 Correct 438 ms 49404 KB Output is correct
26 Correct 427 ms 45296 KB Output is correct
27 Correct 403 ms 44352 KB Output is correct

Subtask #8
0 / 8.0

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