oj.uz

Submission #108890

# Submission time Handle Problem Language Result Execution time Memory
108890 2019-05-02T11:36:05 Z oolimry Duathlon (APIO18_duathlon) C++14
66 / 100
 481 ms 57744 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;
int root = 0;
int cnt = 1;
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 p = -1;
    vi adj;
};

vector<node2> bct; ///block-cut tree
long long ans = 0ll;
long long dp(int u, int p){
    bct[u].dp = bct[u].sz;
    for(int j = 0;j < bct[u].adj.size();j++){
        int v = bct[u].adj[j];
        if(v != p)
            bct[u].dp += dp(v,u);
    }
    return bct[u].dp;
}
void countWays(int u, long long total){
    long long sz = bct[u].sz;
    bct[u].vis = true;
    if(!bct[u].isArti){
        ans += sz * (sz - 1) * (sz + bct[u].adj.size() - 2);
        ans += 2ll * sz * (sz + bct[u].adj.size() - 2) * (total - sz);
    }
    long long others = total - bct[u].dp;
    for(int j = 0;j < bct[u].adj.size();j++){
        int v = bct[u].adj[j];
        if(!bct[v].vis){
            countWays(v,total);
            long long extra = 0ll;
            if(!bct[u].isArti) extra = bct[u].adj.size()-2;
            ans += 2ll * (bct[u].sz + extra) * bct[v].dp * others;
            others += 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;
            root = i;
            dfs(i);
            if(rootChildren > 1) g[i].isArti = true;
            else g[i].isArti = false; ///this line is needed
        }
    }

    vi components[n];
    for(int i = 0;i < biconnected.size();i++){
        node2 nn;
        nn.isArti = false;
        nn.sz = biconnected[i].size();
        bct.push_back(nn);
        for(int j : biconnected[i]){
            components[j].push_back(i);
            // << j << " ";
        }
        //cout << "\n";
    }

    for(int i = 0;i < n;i++){
        if(components[i].size() > 1){
            node2 nn;
            int id = bct.size();
            nn.sz = 1;
            nn.isArti = true;
            for(int j = 0;j < components[i].size();j++){
                nn.adj.push_back(components[i][j]);
                bct[components[i][j]].adj.push_back(id);
                bct[components[i][j]].sz--;
            }
            bct.push_back(nn);
        }
    }
    /*

    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";
    }
    //*/

    for(int i = 0;i < bct.size();i++){
        if(!bct[i].vis) countWays(i,dp(i,-1));
    }
    /*
    long long ans = 0ll;
    for(int i = 0;i < bct.size();i++){
        long long total = bct[bct[i].r].dp - bct[i].sz;
        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:27: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 'long long int dp(int, int)':
count_triplets.cpp:72:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0;j < bct[u].adj.size();j++){
                   ~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void countWays(int, long long int)':
count_triplets.cpp:87:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0;j < bct[u].adj.size();j++){
                   ~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:124:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < biconnected.size();i++){
                   ~~^~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:142:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0;j < components[i].size();j++){
                           ~~^~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:161:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < bct.size();i++){
                   ~~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8164 KB Output is correct
2 Correct 11 ms 8192 KB Output is correct
3 Correct 10 ms 8192 KB Output is correct
4 Correct 12 ms 8192 KB Output is correct
5 Correct 11 ms 8192 KB Output is correct
6 Correct 11 ms 8192 KB Output is correct
7 Correct 9 ms 8192 KB Output is correct
8 Correct 9 ms 8192 KB Output is correct
9 Correct 10 ms 8164 KB Output is correct
10 Correct 45 ms 8192 KB Output is correct
11 Correct 10 ms 8192 KB Output is correct
12 Correct 11 ms 8192 KB Output is correct
13 Correct 10 ms 8192 KB Output is correct
14 Correct 10 ms 8192 KB Output is correct
15 Correct 10 ms 8192 KB Output is correct
16 Correct 9 ms 8192 KB Output is correct
17 Correct 11 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 8 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 10 ms 8164 KB Output is correct
2 Correct 11 ms 8192 KB Output is correct
3 Correct 10 ms 8192 KB Output is correct
4 Correct 12 ms 8192 KB Output is correct
5 Correct 11 ms 8192 KB Output is correct
6 Correct 11 ms 8192 KB Output is correct
7 Correct 9 ms 8192 KB Output is correct
8 Correct 9 ms 8192 KB Output is correct
9 Correct 10 ms 8164 KB Output is correct
10 Correct 45 ms 8192 KB Output is correct
11 Correct 10 ms 8192 KB Output is correct
12 Correct 11 ms 8192 KB Output is correct
13 Correct 10 ms 8192 KB Output is correct
14 Correct 10 ms 8192 KB Output is correct
15 Correct 10 ms 8192 KB Output is correct
16 Correct 9 ms 8192 KB Output is correct
17 Correct 11 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 8 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 250 ms 34940 KB Output is correct
2 Correct 239 ms 34964 KB Output is correct
3 Correct 301 ms 40512 KB Output is correct
4 Correct 307 ms 38052 KB Output is correct
5 Correct 286 ms 36596 KB Output is correct
6 Correct 388 ms 41716 KB Output is correct
7 Correct 395 ms 39484 KB Output is correct
8 Correct 351 ms 41148 KB Output is correct
9 Correct 369 ms 38676 KB Output is correct
10 Correct 307 ms 36672 KB Output is correct
11 Correct 206 ms 33604 KB Output is correct
12 Correct 224 ms 33340 KB Output is correct
13 Correct 227 ms 32876 KB Output is correct
14 Correct 202 ms 32448 KB Output is correct
15 Correct 198 ms 26208 KB Output is correct
16 Correct 172 ms 25944 KB Output is correct
17 Correct 13 ms 10624 KB Output is correct
18 Correct 13 ms 10496 KB Output is correct
19 Correct 14 ms 10596 KB Output is correct
20 Correct 12 ms 10496 KB Output is correct
21 Correct 12 ms 10496 KB Output is correct
22 Correct 14 ms 10496 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 14 ms 8576 KB Output is correct
3 Correct 11 ms 8576 KB Output is correct
4 Correct 14 ms 8704 KB Output is correct
5 Correct 11 ms 8576 KB Output is correct
6 Correct 15 ms 8576 KB Output is correct
7 Correct 12 ms 8576 KB Output is correct
8 Correct 11 ms 8576 KB Output is correct
9 Correct 11 ms 8576 KB Output is correct
10 Correct 11 ms 8576 KB Output is correct
11 Correct 11 ms 8448 KB Output is correct
12 Correct 10 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 10 ms 8320 KB Output is correct
17 Correct 10 ms 8448 KB Output is correct
18 Correct 11 ms 8576 KB Output is correct
19 Correct 10 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 375 ms 48240 KB Output is correct
2 Correct 383 ms 48340 KB Output is correct
3 Correct 339 ms 48184 KB Output is correct
4 Correct 375 ms 48448 KB Output is correct
5 Correct 348 ms 48280 KB Output is correct
6 Correct 481 ms 57744 KB Output is correct
7 Correct 433 ms 51256 KB Output is correct
8 Correct 444 ms 49848 KB Output is correct
9 Correct 414 ms 48308 KB Output is correct
10 Correct 355 ms 48428 KB Output is correct
11 Correct 355 ms 48312 KB Output is correct
12 Correct 314 ms 48352 KB Output is correct
13 Correct 337 ms 48308 KB Output is correct
14 Correct 302 ms 47172 KB Output is correct
15 Correct 229 ms 38708 KB Output is correct
16 Correct 143 ms 30788 KB Output is correct
17 Correct 223 ms 42224 KB Output is correct
18 Correct 247 ms 41768 KB Output is correct
19 Correct 202 ms 42156 KB Output is correct
20 Correct 216 ms 41912 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 13 ms 8576 KB Output is correct
3 Correct 13 ms 8576 KB Output is correct
4 Correct 11 ms 8448 KB Output is correct
5 Correct 11 ms 8448 KB Output is correct
6 Correct 11 ms 8320 KB Output is correct
7 Correct 11 ms 8320 KB Output is correct
8 Correct 13 ms 8320 KB Output is correct
9 Correct 10 ms 8320 KB Output is correct
10 Correct 10 ms 8292 KB Output is correct
11 Correct 13 ms 8320 KB Output is correct
12 Correct 11 ms 8576 KB Output is correct
13 Correct 11 ms 8576 KB Output is correct
14 Correct 11 ms 8576 KB Output is correct
15 Correct 11 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 13 ms 8448 KB Output is correct
19 Correct 11 ms 8448 KB Output is correct
20 Correct 11 ms 8448 KB Output is correct
21 Correct 10 ms 8576 KB Output is correct
22 Correct 10 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 9 ms 8192 KB Output is correct
26 Correct 11 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 348 ms 48308 KB Output is correct
2 Correct 365 ms 47908 KB Output is correct
3 Correct 369 ms 47544 KB Output is correct
4 Correct 339 ms 36820 KB Output is correct
5 Correct 262 ms 30784 KB Output is correct
6 Correct 294 ms 28492 KB Output is correct
7 Correct 266 ms 28236 KB Output is correct
8 Correct 238 ms 25292 KB Output is correct
9 Correct 220 ms 25212 KB Output is correct
10 Correct 206 ms 24060 KB Output is correct
11 Correct 215 ms 23096 KB Output is correct
12 Correct 234 ms 22248 KB Output is correct
13 Correct 211 ms 22136 KB Output is correct
14 Correct 249 ms 23800 KB Output is correct
15 Correct 437 ms 51420 KB Output is correct
16 Correct 373 ms 49208 KB Output is correct
17 Correct 384 ms 43700 KB Output is correct
18 Correct 403 ms 41528 KB Output is correct
19 Correct 328 ms 36792 KB Output is correct
20 Correct 303 ms 36788 KB Output is correct
21 Correct 341 ms 36788 KB Output is correct
22 Correct 277 ms 34580 KB Output is correct
23 Correct 249 ms 30020 KB Output is correct
24 Correct 346 ms 41020 KB Output is correct
25 Correct 349 ms 41148 KB Output is correct
26 Correct 292 ms 38068 KB Output is correct
27 Correct 387 ms 38068 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8164 KB Output is correct
2 Correct 11 ms 8192 KB Output is correct
3 Correct 10 ms 8192 KB Output is correct
4 Correct 12 ms 8192 KB Output is correct
5 Correct 11 ms 8192 KB Output is correct
6 Correct 11 ms 8192 KB Output is correct
7 Correct 9 ms 8192 KB Output is correct
8 Correct 9 ms 8192 KB Output is correct
9 Correct 10 ms 8164 KB Output is correct
10 Correct 45 ms 8192 KB Output is correct
11 Correct 10 ms 8192 KB Output is correct
12 Correct 11 ms 8192 KB Output is correct
13 Correct 10 ms 8192 KB Output is correct
14 Correct 10 ms 8192 KB Output is correct
15 Correct 10 ms 8192 KB Output is correct
16 Correct 9 ms 8192 KB Output is correct
17 Correct 11 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 8 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 10 ms 8164 KB Output is correct
2 Correct 11 ms 8192 KB Output is correct
3 Correct 10 ms 8192 KB Output is correct
4 Correct 12 ms 8192 KB Output is correct
5 Correct 11 ms 8192 KB Output is correct
6 Correct 11 ms 8192 KB Output is correct
7 Correct 9 ms 8192 KB Output is correct
8 Correct 9 ms 8192 KB Output is correct
9 Correct 10 ms 8164 KB Output is correct
10 Correct 45 ms 8192 KB Output is correct
11 Correct 10 ms 8192 KB Output is correct
12 Correct 11 ms 8192 KB Output is correct
13 Correct 10 ms 8192 KB Output is correct
14 Correct 10 ms 8192 KB Output is correct
15 Correct 10 ms 8192 KB Output is correct
16 Correct 9 ms 8192 KB Output is correct
17 Correct 11 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 8 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 -