oj.uz

Submission #108715

# Submission time Handle Problem Language Result Execution time Memory
108715 2019-05-01T06:53:20 Z oolimry Duathlon (APIO18_duathlon) C++14
66 / 100
 504 ms 57268 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;
            if(!bct[i].isArti) extra = 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++){
                       ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8192 KB Output is correct
2 Correct 10 ms 8192 KB Output is correct
3 Correct 11 ms 8192 KB Output is correct
4 Correct 11 ms 8192 KB Output is correct
5 Correct 10 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 10 ms 8192 KB Output is correct
9 Correct 9 ms 8232 KB Output is correct
10 Correct 9 ms 8192 KB Output is correct
11 Correct 10 ms 8192 KB Output is correct
12 Correct 9 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 9 ms 8192 KB Output is correct
16 Correct 9 ms 8192 KB Output is correct
17 Correct 8 ms 8192 KB Output is correct
18 Correct 9 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 9 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 10 ms 8192 KB Output is correct
2 Correct 10 ms 8192 KB Output is correct
3 Correct 11 ms 8192 KB Output is correct
4 Correct 11 ms 8192 KB Output is correct
5 Correct 10 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 10 ms 8192 KB Output is correct
9 Correct 9 ms 8232 KB Output is correct
10 Correct 9 ms 8192 KB Output is correct
11 Correct 10 ms 8192 KB Output is correct
12 Correct 9 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 9 ms 8192 KB Output is correct
16 Correct 9 ms 8192 KB Output is correct
17 Correct 8 ms 8192 KB Output is correct
18 Correct 9 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 9 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 221 ms 32396 KB Output is correct
2 Correct 249 ms 32360 KB Output is correct
3 Correct 357 ms 40180 KB Output is correct
4 Correct 293 ms 36396 KB Output is correct
5 Correct 306 ms 36088 KB Output is correct
6 Correct 353 ms 39660 KB Output is correct
7 Correct 377 ms 38844 KB Output is correct
8 Correct 333 ms 40252 KB Output is correct
9 Correct 316 ms 37460 KB Output is correct
10 Correct 310 ms 35664 KB Output is correct
11 Correct 268 ms 31552 KB Output is correct
12 Correct 215 ms 31168 KB Output is correct
13 Correct 198 ms 30892 KB Output is correct
14 Correct 212 ms 30332 KB Output is correct
15 Correct 150 ms 24188 KB Output is correct
16 Correct 155 ms 23988 KB Output is correct
17 Correct 11 ms 8192 KB Output is correct
18 Correct 32 ms 8192 KB Output is correct
19 Correct 11 ms 8164 KB Output is correct
20 Correct 10 ms 8192 KB Output is correct
21 Correct 10 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 11 ms 8576 KB Output is correct
2 Correct 12 ms 8572 KB Output is correct
3 Correct 13 ms 8676 KB Output is correct
4 Correct 12 ms 8704 KB Output is correct
5 Correct 12 ms 8700 KB Output is correct
6 Correct 11 ms 8576 KB Output is correct
7 Correct 11 ms 8576 KB Output is correct
8 Correct 15 ms 8576 KB Output is correct
9 Correct 13 ms 8576 KB Output is correct
10 Correct 11 ms 8576 KB Output is correct
11 Correct 11 ms 8576 KB Output is correct
12 Correct 14 ms 8572 KB Output is correct
13 Correct 11 ms 8576 KB Output is correct
14 Correct 12 ms 8576 KB Output is correct
15 Correct 13 ms 8448 KB Output is correct
16 Correct 10 ms 8320 KB Output is correct
17 Correct 14 ms 8448 KB Output is correct
18 Correct 12 ms 8448 KB Output is correct
19 Correct 14 ms 8448 KB Output is correct
20 Correct 12 ms 8448 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 48812 KB Output is correct
2 Correct 360 ms 48768 KB Output is correct
3 Correct 372 ms 48568 KB Output is correct
4 Correct 369 ms 48712 KB Output is correct
5 Correct 391 ms 48692 KB Output is correct
6 Correct 504 ms 57268 KB Output is correct
7 Correct 471 ms 54268 KB Output is correct
8 Correct 446 ms 52764 KB Output is correct
9 Correct 441 ms 51508 KB Output is correct
10 Correct 413 ms 48692 KB Output is correct
11 Correct 397 ms 48784 KB Output is correct
12 Correct 465 ms 48712 KB Output is correct
13 Correct 377 ms 48748 KB Output is correct
14 Correct 337 ms 47036 KB Output is correct
15 Correct 347 ms 37812 KB Output is correct
16 Correct 197 ms 29252 KB Output is correct
17 Correct 208 ms 40340 KB Output is correct
18 Correct 255 ms 40292 KB Output is correct
19 Correct 244 ms 40108 KB Output is correct
20 Correct 239 ms 40164 KB Output is correct

Subtask #6
15.0 / 15.0

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

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 48776 KB Output is correct
2 Correct 373 ms 48692 KB Output is correct
3 Correct 375 ms 47416 KB Output is correct
4 Correct 362 ms 34032 KB Output is correct
5 Correct 297 ms 27592 KB Output is correct
6 Correct 264 ms 24620 KB Output is correct
7 Correct 272 ms 24016 KB Output is correct
8 Correct 225 ms 20632 KB Output is correct
9 Correct 208 ms 20432 KB Output is correct
10 Correct 220 ms 19052 KB Output is correct
11 Correct 205 ms 17832 KB Output is correct
12 Correct 191 ms 17272 KB Output is correct
13 Correct 241 ms 17272 KB Output is correct
14 Correct 304 ms 20732 KB Output is correct
15 Correct 417 ms 53704 KB Output is correct
16 Correct 412 ms 51640 KB Output is correct
17 Correct 441 ms 44520 KB Output is correct
18 Correct 390 ms 42296 KB Output is correct
19 Correct 317 ms 33860 KB Output is correct
20 Correct 320 ms 33860 KB Output is correct
21 Correct 326 ms 33984 KB Output is correct
22 Correct 328 ms 32320 KB Output is correct
23 Correct 231 ms 26948 KB Output is correct
24 Correct 325 ms 39740 KB Output is correct
25 Correct 301 ms 39480 KB Output is correct
26 Correct 317 ms 37348 KB Output is correct
27 Correct 338 ms 37172 KB Output is correct

Subtask #8
0 / 8.0

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