oj.uz

Submission #108714

# Submission time Handle Problem Language Result Execution time Memory
108714 2019-05-01T06:51:02 Z oolimry Duathlon (APIO18_duathlon) C++14
66 / 100
 528 ms 57272 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;
        }

        for(int j = 0;j < branches.size();j++){
            long long extra = 0, extra2 = 0;
            if(!bct[i].isArti) extra = max(0ll,(long long)(bct[i].adj.size())-2);
            ans += branches[j] * (total - branches[j]) * (bct[i].sz + extra);
        }


        //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 < branches.size();j++){
                       ~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:200:34: warning: unused variable 'extra2' [-Wunused-variable]
             long long extra = 0, extra2 = 0;
                                  ^~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8192 KB Output is correct
2 Correct 11 ms 8192 KB Output is correct
3 Correct 11 ms 8192 KB Output is correct
4 Correct 10 ms 8192 KB Output is correct
5 Correct 10 ms 8064 KB Output is correct
6 Correct 10 ms 8192 KB Output is correct
7 Correct 10 ms 8192 KB Output is correct
8 Correct 10 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 11 ms 8192 KB Output is correct
12 Correct 11 ms 8192 KB Output is correct
13 Correct 9 ms 8080 KB Output is correct
14 Correct 9 ms 8192 KB Output is correct
15 Correct 12 ms 8192 KB Output is correct
16 Correct 10 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 8080 KB Output is correct
20 Correct 10 ms 8192 KB Output is correct
21 Correct 10 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 11 ms 8192 KB Output is correct
2 Correct 11 ms 8192 KB Output is correct
3 Correct 11 ms 8192 KB Output is correct
4 Correct 10 ms 8192 KB Output is correct
5 Correct 10 ms 8064 KB Output is correct
6 Correct 10 ms 8192 KB Output is correct
7 Correct 10 ms 8192 KB Output is correct
8 Correct 10 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 11 ms 8192 KB Output is correct
12 Correct 11 ms 8192 KB Output is correct
13 Correct 9 ms 8080 KB Output is correct
14 Correct 9 ms 8192 KB Output is correct
15 Correct 12 ms 8192 KB Output is correct
16 Correct 10 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 8080 KB Output is correct
20 Correct 10 ms 8192 KB Output is correct
21 Correct 10 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 243 ms 32456 KB Output is correct
2 Correct 236 ms 32564 KB Output is correct
3 Correct 329 ms 40212 KB Output is correct
4 Correct 332 ms 36552 KB Output is correct
5 Correct 299 ms 36088 KB Output is correct
6 Correct 398 ms 39792 KB Output is correct
7 Correct 397 ms 38972 KB Output is correct
8 Correct 378 ms 40392 KB Output is correct
9 Correct 414 ms 37560 KB Output is correct
10 Correct 370 ms 35776 KB Output is correct
11 Correct 306 ms 31552 KB Output is correct
12 Correct 264 ms 31320 KB Output is correct
13 Correct 179 ms 30912 KB Output is correct
14 Correct 237 ms 30564 KB Output is correct
15 Correct 158 ms 24388 KB Output is correct
16 Correct 210 ms 24132 KB Output is correct
17 Correct 11 ms 8192 KB Output is correct
18 Correct 15 ms 8192 KB Output is correct
19 Correct 11 ms 8192 KB Output is correct
20 Correct 11 ms 8192 KB Output is correct
21 Correct 11 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 14 ms 8576 KB Output is correct
2 Correct 13 ms 8592 KB Output is correct
3 Correct 13 ms 8576 KB Output is correct
4 Correct 14 ms 8704 KB Output is correct
5 Correct 12 ms 8568 KB Output is correct
6 Correct 14 ms 8576 KB Output is correct
7 Correct 11 ms 8704 KB Output is correct
8 Correct 15 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 11 ms 8576 KB Output is correct
12 Correct 12 ms 8572 KB Output is correct
13 Correct 11 ms 8572 KB Output is correct
14 Correct 11 ms 8448 KB Output is correct
15 Correct 13 ms 8448 KB Output is correct
16 Correct 11 ms 8320 KB Output is correct
17 Correct 10 ms 8448 KB Output is correct
18 Correct 11 ms 8448 KB Output is correct
19 Correct 13 ms 8448 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 467 ms 48728 KB Output is correct
2 Correct 371 ms 48824 KB Output is correct
3 Correct 396 ms 48796 KB Output is correct
4 Correct 406 ms 48796 KB Output is correct
5 Correct 441 ms 48824 KB Output is correct
6 Correct 528 ms 57272 KB Output is correct
7 Correct 435 ms 54428 KB Output is correct
8 Correct 428 ms 52948 KB Output is correct
9 Correct 374 ms 51632 KB Output is correct
10 Correct 400 ms 48820 KB Output is correct
11 Correct 396 ms 48780 KB Output is correct
12 Correct 393 ms 48756 KB Output is correct
13 Correct 374 ms 48756 KB Output is correct
14 Correct 337 ms 47188 KB Output is correct
15 Correct 332 ms 37948 KB Output is correct
16 Correct 156 ms 29436 KB Output is correct
17 Correct 222 ms 40624 KB Output is correct
18 Correct 239 ms 40600 KB Output is correct
19 Correct 269 ms 40368 KB Output is correct
20 Correct 325 ms 40252 KB Output is correct

Subtask #6
15.0 / 15.0

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

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 48824 KB Output is correct
2 Correct 458 ms 48740 KB Output is correct
3 Correct 410 ms 47560 KB Output is correct
4 Correct 326 ms 34116 KB Output is correct
5 Correct 323 ms 27584 KB Output is correct
6 Correct 306 ms 24668 KB Output is correct
7 Correct 261 ms 24264 KB Output is correct
8 Correct 223 ms 20684 KB Output is correct
9 Correct 225 ms 20444 KB Output is correct
10 Correct 309 ms 19104 KB Output is correct
11 Correct 213 ms 18060 KB Output is correct
12 Correct 186 ms 17400 KB Output is correct
13 Correct 176 ms 17464 KB Output is correct
14 Correct 178 ms 20668 KB Output is correct
15 Correct 501 ms 53980 KB Output is correct
16 Correct 388 ms 51640 KB Output is correct
17 Correct 480 ms 44856 KB Output is correct
18 Correct 424 ms 42296 KB Output is correct
19 Correct 387 ms 34188 KB Output is correct
20 Correct 320 ms 33984 KB Output is correct
21 Correct 408 ms 34036 KB Output is correct
22 Correct 341 ms 32388 KB Output is correct
23 Correct 278 ms 27080 KB Output is correct
24 Correct 326 ms 39740 KB Output is correct
25 Correct 374 ms 39768 KB Output is correct
26 Correct 316 ms 37484 KB Output is correct
27 Correct 294 ms 37176 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 11 ms 8192 KB Output is correct
3 Correct 11 ms 8192 KB Output is correct
4 Correct 10 ms 8192 KB Output is correct
5 Correct 10 ms 8064 KB Output is correct
6 Correct 10 ms 8192 KB Output is correct
7 Correct 10 ms 8192 KB Output is correct
8 Correct 10 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 11 ms 8192 KB Output is correct
12 Correct 11 ms 8192 KB Output is correct
13 Correct 9 ms 8080 KB Output is correct
14 Correct 9 ms 8192 KB Output is correct
15 Correct 12 ms 8192 KB Output is correct
16 Correct 10 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 8080 KB Output is correct
20 Correct 10 ms 8192 KB Output is correct
21 Correct 10 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 11 ms 8192 KB Output is correct
2 Correct 11 ms 8192 KB Output is correct
3 Correct 11 ms 8192 KB Output is correct
4 Correct 10 ms 8192 KB Output is correct
5 Correct 10 ms 8064 KB Output is correct
6 Correct 10 ms 8192 KB Output is correct
7 Correct 10 ms 8192 KB Output is correct
8 Correct 10 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 11 ms 8192 KB Output is correct
12 Correct 11 ms 8192 KB Output is correct
13 Correct 9 ms 8080 KB Output is correct
14 Correct 9 ms 8192 KB Output is correct
15 Correct 12 ms 8192 KB Output is correct
16 Correct 10 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 8080 KB Output is correct
20 Correct 10 ms 8192 KB Output is correct
21 Correct 10 ms 8192 KB Output is correct
22 Incorrect 10 ms 8192 KB Output isn't correct
23 Halted 0 ms 0 KB -