oj.uz

Submission #108838

# Submission time Handle Problem Language Result Execution time Memory
108838 2019-05-02T09:33:24 Z oolimry Duathlon (APIO18_duathlon) C++14
58 / 100
 486 ms 65544 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";
    }

    if(artis.size() == 0) assert(false);
    for(int i = 0;i < bct.size();i++){
        root = i;
        dp(i);
    }

    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 = 0ll;
                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:135:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < bct.size();i++){
                   ~~^~~~~~~~~~~~
count_triplets.cpp:141:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < bct.size();i++){
                   ~~^~~~~~~~~~~~
count_triplets.cpp:145:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < bct[i].adj.size();j++){
                       ~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp:155: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:193: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 Runtime error 24 ms 16128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 16128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 222 ms 65544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8576 KB Output is correct
2 Correct 11 ms 8576 KB Output is correct
3 Correct 11 ms 8576 KB Output is correct
4 Correct 11 ms 8704 KB Output is correct
5 Correct 12 ms 8576 KB Output is correct
6 Correct 10 ms 8576 KB Output is correct
7 Correct 12 ms 8704 KB Output is correct
8 Correct 11 ms 8548 KB Output is correct
9 Correct 12 ms 8604 KB Output is correct
10 Correct 13 ms 8576 KB Output is correct
11 Correct 14 ms 8572 KB Output is correct
12 Correct 14 ms 8576 KB Output is correct
13 Correct 10 ms 8576 KB Output is correct
14 Correct 10 ms 8576 KB Output is correct
15 Correct 11 ms 8448 KB Output is correct
16 Correct 12 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 8448 KB Output is correct
20 Correct 13 ms 8496 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 49856 KB Output is correct
2 Correct 483 ms 49872 KB Output is correct
3 Correct 369 ms 49720 KB Output is correct
4 Correct 418 ms 49928 KB Output is correct
5 Correct 447 ms 49732 KB Output is correct
6 Correct 486 ms 58292 KB Output is correct
7 Correct 439 ms 55356 KB Output is correct
8 Correct 450 ms 54072 KB Output is correct
9 Correct 473 ms 52664 KB Output is correct
10 Correct 429 ms 49880 KB Output is correct
11 Correct 361 ms 49936 KB Output is correct
12 Correct 397 ms 49868 KB Output is correct
13 Correct 394 ms 50024 KB Output is correct
14 Correct 361 ms 48028 KB Output is correct
15 Correct 325 ms 38708 KB Output is correct
16 Correct 165 ms 29884 KB Output is correct
17 Correct 222 ms 41712 KB Output is correct
18 Correct 236 ms 41472 KB Output is correct
19 Correct 228 ms 41412 KB Output is correct
20 Correct 202 ms 41404 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 11 ms 8576 KB Output is correct
3 Correct 14 ms 8476 KB Output is correct
4 Correct 12 ms 8448 KB Output is correct
5 Correct 12 ms 8448 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 8320 KB Output is correct
9 Correct 10 ms 8320 KB Output is correct
10 Correct 12 ms 8320 KB Output is correct
11 Correct 9 ms 8320 KB Output is correct
12 Correct 12 ms 8576 KB Output is correct
13 Correct 10 ms 8576 KB Output is correct
14 Correct 13 ms 8576 KB Output is correct
15 Correct 12 ms 8576 KB Output is correct
16 Correct 14 ms 8448 KB Output is correct
17 Correct 16 ms 8456 KB Output is correct
18 Correct 12 ms 8448 KB Output is correct
19 Correct 13 ms 8320 KB Output is correct
20 Correct 15 ms 8320 KB Output is correct
21 Correct 13 ms 8448 KB Output is correct
22 Correct 14 ms 8448 KB Output is correct
23 Correct 14 ms 8448 KB Output is correct
24 Correct 13 ms 8448 KB Output is correct
25 Correct 13 ms 8192 KB Output is correct
26 Correct 8 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 399 ms 49840 KB Output is correct
2 Correct 360 ms 49720 KB Output is correct
3 Correct 367 ms 48692 KB Output is correct
4 Correct 342 ms 35484 KB Output is correct
5 Correct 326 ms 28864 KB Output is correct
6 Correct 258 ms 26044 KB Output is correct
7 Correct 260 ms 25288 KB Output is correct
8 Correct 230 ms 21812 KB Output is correct
9 Correct 292 ms 21684 KB Output is correct
10 Correct 197 ms 20304 KB Output is correct
11 Correct 179 ms 19212 KB Output is correct
12 Correct 174 ms 18552 KB Output is correct
13 Correct 171 ms 18500 KB Output is correct
14 Correct 180 ms 21880 KB Output is correct
15 Correct 433 ms 55000 KB Output is correct
16 Correct 387 ms 53048 KB Output is correct
17 Correct 397 ms 46208 KB Output is correct
18 Correct 437 ms 43764 KB Output is correct
19 Correct 336 ms 35516 KB Output is correct
20 Correct 347 ms 35412 KB Output is correct
21 Correct 403 ms 35548 KB Output is correct
22 Correct 311 ms 33784 KB Output is correct
23 Correct 250 ms 28140 KB Output is correct
24 Correct 320 ms 41020 KB Output is correct
25 Correct 315 ms 40888 KB Output is correct
26 Correct 376 ms 38832 KB Output is correct
27 Correct 333 ms 38708 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 16128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 16128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -