oj.uz

Submission #108692

# Submission time Handle Problem Language Result Execution time Memory
108692 2019-05-01T04:57:13 Z oolimry Duathlon (APIO18_duathlon) C++14
31 / 100
 510 ms 58004 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;
        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);
            }
        }
        branches.push_back(bct[bct[i].r].dp - bct[i].dp);
        for(int j = 0;j < branches.size();j++) total += branches[j];

        for(int j = 0;j < branches.size();j++){
            //cout << i << " " << branches[j] << "\n";
            ///branch1 to self to branch2
            ans += branches[j] * (total - branches[j]) * bct[i].sz;

            ///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);
            }
        }


        ///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 << ans << "\n";
    }
    cout << ans;
}

/*
8 7
8 5
8 1
7 5
8 6
3 1
3 2
8 3
*/

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:150:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < bct[i].adj.size();j++){
                       ~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp:156: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:158: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 10 ms 8192 KB Output is correct
5 Correct 12 ms 8192 KB Output is correct
6 Correct 10 ms 8192 KB Output is correct
7 Incorrect 11 ms 8192 KB Output isn't correct
8 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 10 ms 8192 KB Output is correct
5 Correct 12 ms 8192 KB Output is correct
6 Correct 10 ms 8192 KB Output is correct
7 Incorrect 11 ms 8192 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 33268 KB Output is correct
2 Correct 201 ms 33216 KB Output is correct
3 Correct 329 ms 41076 KB Output is correct
4 Correct 264 ms 37708 KB Output is correct
5 Correct 287 ms 37304 KB Output is correct
6 Correct 340 ms 40892 KB Output is correct
7 Correct 363 ms 40056 KB Output is correct
8 Correct 389 ms 41404 KB Output is correct
9 Correct 379 ms 38668 KB Output is correct
10 Correct 316 ms 36672 KB Output is correct
11 Correct 231 ms 32448 KB Output is correct
12 Correct 258 ms 32192 KB Output is correct
13 Correct 231 ms 31680 KB Output is correct
14 Correct 195 ms 31360 KB Output is correct
15 Correct 155 ms 25032 KB Output is correct
16 Correct 181 ms 24596 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 Correct 10 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 8464 KB Output is correct
3 Correct 12 ms 8828 KB Output is correct
4 Correct 12 ms 8704 KB Output is correct
5 Correct 11 ms 8576 KB Output is correct
6 Correct 12 ms 8576 KB Output is correct
7 Correct 14 ms 8704 KB Output is correct
8 Correct 14 ms 8576 KB Output is correct
9 Correct 14 ms 8576 KB Output is correct
10 Correct 12 ms 8576 KB Output is correct
11 Correct 11 ms 8576 KB Output is correct
12 Correct 13 ms 8576 KB Output is correct
13 Correct 12 ms 8576 KB Output is correct
14 Correct 11 ms 8576 KB Output is correct
15 Correct 11 ms 8448 KB Output is correct
16 Correct 11 ms 8320 KB Output is correct
17 Correct 14 ms 8448 KB Output is correct
18 Correct 14 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 391 ms 49440 KB Output is correct
2 Correct 365 ms 49584 KB Output is correct
3 Correct 361 ms 49564 KB Output is correct
4 Correct 345 ms 49460 KB Output is correct
5 Correct 363 ms 49460 KB Output is correct
6 Correct 510 ms 58004 KB Output is correct
7 Correct 445 ms 55136 KB Output is correct
8 Correct 394 ms 53668 KB Output is correct
9 Correct 379 ms 52148 KB Output is correct
10 Correct 363 ms 49620 KB Output is correct
11 Correct 455 ms 49904 KB Output is correct
12 Correct 402 ms 49924 KB Output is correct
13 Correct 410 ms 49848 KB Output is correct
14 Correct 345 ms 48180 KB Output is correct
15 Correct 318 ms 38688 KB Output is correct
16 Correct 171 ms 30016 KB Output is correct
17 Correct 212 ms 41628 KB Output is correct
18 Correct 218 ms 41648 KB Output is correct
19 Correct 238 ms 41564 KB Output is correct
20 Correct 217 ms 41468 KB Output is correct

Subtask #6
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 Incorrect 11 ms 8448 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 49556 KB Output is correct
2 Correct 466 ms 49396 KB Output is correct
3 Incorrect 392 ms 48312 KB Output isn't correct
4 Halted 0 ms 0 KB -

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 10 ms 8192 KB Output is correct
5 Correct 12 ms 8192 KB Output is correct
6 Correct 10 ms 8192 KB Output is correct
7 Incorrect 11 ms 8192 KB Output isn't correct
8 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 10 ms 8192 KB Output is correct
5 Correct 12 ms 8192 KB Output is correct
6 Correct 10 ms 8192 KB Output is correct
7 Incorrect 11 ms 8192 KB Output isn't correct
8 Halted 0 ms 0 KB -