oj.uz

Submission #108710

# Submission time Handle Problem Language Result Execution time Memory
108710 2019-05-01T06:28:24 Z oolimry Duathlon (APIO18_duathlon) C++14
66 / 100
 578 ms 57784 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 = 0ll;
        if(!bct[i].isArti) extra = max(0ll,(long long)(bct[i].adj.size())-2);
        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 - 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);
        //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:164: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 9 ms 8192 KB Output is correct
4 Correct 10 ms 8192 KB Output is correct
5 Correct 11 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 9 ms 8192 KB Output is correct
10 Correct 9 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 11 ms 8192 KB Output is correct
15 Correct 9 ms 8192 KB Output is correct
16 Correct 12 ms 8164 KB Output is correct
17 Correct 12 ms 8192 KB Output is correct
18 Correct 9 ms 8192 KB Output is correct
19 Correct 13 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 10 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 10 ms 8192 KB Output is correct
5 Correct 11 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 9 ms 8192 KB Output is correct
10 Correct 9 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 11 ms 8192 KB Output is correct
15 Correct 9 ms 8192 KB Output is correct
16 Correct 12 ms 8164 KB Output is correct
17 Correct 12 ms 8192 KB Output is correct
18 Correct 9 ms 8192 KB Output is correct
19 Correct 13 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 260 ms 33212 KB Output is correct
2 Correct 251 ms 33160 KB Output is correct
3 Correct 401 ms 41052 KB Output is correct
4 Correct 268 ms 36936 KB Output is correct
5 Correct 306 ms 36576 KB Output is correct
6 Correct 415 ms 40316 KB Output is correct
7 Correct 401 ms 39476 KB Output is correct
8 Correct 374 ms 40776 KB Output is correct
9 Correct 350 ms 38072 KB Output is correct
10 Correct 411 ms 36020 KB Output is correct
11 Correct 251 ms 31916 KB Output is correct
12 Correct 250 ms 31688 KB Output is correct
13 Correct 215 ms 31256 KB Output is correct
14 Correct 244 ms 30912 KB Output is correct
15 Correct 142 ms 24872 KB Output is correct
16 Correct 172 ms 24384 KB Output is correct
17 Correct 12 ms 8192 KB Output is correct
18 Correct 13 ms 8192 KB Output is correct
19 Correct 12 ms 8192 KB Output is correct
20 Correct 12 ms 8192 KB Output is correct
21 Correct 11 ms 8164 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 8572 KB Output is correct
2 Correct 14 ms 8576 KB Output is correct
3 Correct 11 ms 8576 KB Output is correct
4 Correct 13 ms 8704 KB Output is correct
5 Correct 12 ms 8576 KB Output is correct
6 Correct 11 ms 8576 KB Output is correct
7 Correct 13 ms 8704 KB Output is correct
8 Correct 13 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 15 ms 8576 KB Output is correct
12 Correct 12 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 12 ms 8448 KB Output is correct
16 Correct 11 ms 8320 KB Output is correct
17 Correct 11 ms 8448 KB Output is correct
18 Correct 12 ms 8448 KB Output is correct
19 Correct 11 ms 8448 KB Output is correct
20 Correct 11 ms 8448 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 49360 KB Output is correct
2 Correct 406 ms 49592 KB Output is correct
3 Correct 431 ms 49520 KB Output is correct
4 Correct 413 ms 49460 KB Output is correct
5 Correct 413 ms 49464 KB Output is correct
6 Correct 578 ms 57784 KB Output is correct
7 Correct 512 ms 55200 KB Output is correct
8 Correct 479 ms 53656 KB Output is correct
9 Correct 397 ms 52152 KB Output is correct
10 Correct 356 ms 49508 KB Output is correct
11 Correct 449 ms 49184 KB Output is correct
12 Correct 422 ms 49116 KB Output is correct
13 Correct 413 ms 49080 KB Output is correct
14 Correct 393 ms 47672 KB Output is correct
15 Correct 336 ms 38292 KB Output is correct
16 Correct 187 ms 29760 KB Output is correct
17 Correct 282 ms 41040 KB Output is correct
18 Correct 210 ms 40752 KB Output is correct
19 Correct 226 ms 40628 KB Output is correct
20 Correct 253 ms 40656 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8572 KB Output is correct
2 Correct 12 ms 8576 KB Output is correct
3 Correct 13 ms 8664 KB Output is correct
4 Correct 13 ms 8448 KB Output is correct
5 Correct 11 ms 8448 KB Output is correct
6 Correct 12 ms 8320 KB Output is correct
7 Correct 28 ms 8320 KB Output is correct
8 Correct 11 ms 8320 KB Output is correct
9 Correct 11 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 11 ms 8576 KB Output is correct
13 Correct 12 ms 8576 KB Output is correct
14 Correct 10 ms 8576 KB Output is correct
15 Correct 11 ms 8576 KB Output is correct
16 Correct 16 ms 8448 KB Output is correct
17 Correct 14 ms 8576 KB Output is correct
18 Correct 12 ms 8448 KB Output is correct
19 Correct 11 ms 8448 KB Output is correct
20 Correct 12 ms 8392 KB Output is correct
21 Correct 10 ms 8576 KB Output is correct
22 Correct 12 ms 8576 KB Output is correct
23 Correct 11 ms 8448 KB Output is correct
24 Correct 11 ms 8448 KB Output is correct
25 Correct 10 ms 8192 KB Output is correct
26 Correct 11 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 452 ms 49452 KB Output is correct
2 Correct 474 ms 49468 KB Output is correct
3 Correct 465 ms 48056 KB Output is correct
4 Correct 462 ms 35616 KB Output is correct
5 Correct 299 ms 28856 KB Output is correct
6 Correct 318 ms 25960 KB Output is correct
7 Correct 260 ms 25420 KB Output is correct
8 Correct 264 ms 22064 KB Output is correct
9 Correct 215 ms 21584 KB Output is correct
10 Correct 213 ms 20304 KB Output is correct
11 Correct 209 ms 19340 KB Output is correct
12 Correct 199 ms 18524 KB Output is correct
13 Correct 215 ms 18680 KB Output is correct
14 Correct 243 ms 22056 KB Output is correct
15 Correct 543 ms 55108 KB Output is correct
16 Correct 417 ms 53020 KB Output is correct
17 Correct 439 ms 46136 KB Output is correct
18 Correct 520 ms 43792 KB Output is correct
19 Correct 408 ms 35604 KB Output is correct
20 Correct 426 ms 35464 KB Output is correct
21 Correct 391 ms 35560 KB Output is correct
22 Correct 307 ms 33744 KB Output is correct
23 Correct 234 ms 28224 KB Output is correct
24 Correct 299 ms 41092 KB Output is correct
25 Correct 324 ms 40992 KB Output is correct
26 Correct 303 ms 38848 KB Output is correct
27 Correct 312 ms 38580 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 9 ms 8192 KB Output is correct
4 Correct 10 ms 8192 KB Output is correct
5 Correct 11 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 9 ms 8192 KB Output is correct
10 Correct 9 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 11 ms 8192 KB Output is correct
15 Correct 9 ms 8192 KB Output is correct
16 Correct 12 ms 8164 KB Output is correct
17 Correct 12 ms 8192 KB Output is correct
18 Correct 9 ms 8192 KB Output is correct
19 Correct 13 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 10 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 10 ms 8192 KB Output is correct
5 Correct 11 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 9 ms 8192 KB Output is correct
10 Correct 9 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 11 ms 8192 KB Output is correct
15 Correct 9 ms 8192 KB Output is correct
16 Correct 12 ms 8164 KB Output is correct
17 Correct 12 ms 8192 KB Output is correct
18 Correct 9 ms 8192 KB Output is correct
19 Correct 13 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 -