oj.uz

Submission #131111

# Submission time Handle Problem Language Result Execution time Memory
131111 2019-07-16T13:34:00 Z oolimry Duathlon (APIO18_duathlon) C++14
31 / 100
 460 ms 58296 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);
            }
        }
        else if(v != g[u].parent){
            g[u].low = min(g[u].low,g[v].depth); ///g[v].depth not num!!!!!!
        }
        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()
{
    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++){
            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);
    }
    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 = 0ll;
        if(!bct[i].isArti) extra = max(0ll,(long long)(bct[i].adj.size())-2);
        for(int j = 0;j < branches.size();j++){

            ///branch1 to self or neighbor articulation point 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];


            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);
    }
    cout << ans;
}

Compilation message

count_triplets.cpp: In function 'void dfs(int)':
count_triplets.cpp:24: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:70: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:113:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < biconnected.size();i++){
                   ~~^~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:126:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < bct.size();i++){
                   ~~^~~~~~~~~~~~
count_triplets.cpp:132:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < bct.size();i++){
                   ~~^~~~~~~~~~~~
count_triplets.cpp:136:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < bct[i].adj.size();j++){
                       ~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp:146: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:149:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < branches.size();j++){
                       ~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:147:19: warning: variable 'extra' set but not used [-Wunused-but-set-variable]
         long long extra = 0ll;
                   ^~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8312 KB Output is correct
2 Correct 9 ms 8160 KB Output is correct
3 Correct 9 ms 8184 KB Output is correct
4 Correct 9 ms 8184 KB Output is correct
5 Correct 9 ms 8184 KB Output is correct
6 Correct 9 ms 8184 KB Output is correct
7 Incorrect 9 ms 8188 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8312 KB Output is correct
2 Correct 9 ms 8160 KB Output is correct
3 Correct 9 ms 8184 KB Output is correct
4 Correct 9 ms 8184 KB Output is correct
5 Correct 9 ms 8184 KB Output is correct
6 Correct 9 ms 8184 KB Output is correct
7 Incorrect 9 ms 8188 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 223 ms 33592 KB Output is correct
2 Correct 258 ms 33536 KB Output is correct
3 Correct 333 ms 41308 KB Output is correct
4 Correct 276 ms 37688 KB Output is correct
5 Correct 285 ms 37340 KB Output is correct
6 Correct 344 ms 40960 KB Output is correct
7 Correct 357 ms 40156 KB Output is correct
8 Correct 356 ms 41504 KB Output is correct
9 Correct 359 ms 38840 KB Output is correct
10 Correct 336 ms 36800 KB Output is correct
11 Correct 243 ms 32488 KB Output is correct
12 Correct 246 ms 32332 KB Output is correct
13 Correct 215 ms 31680 KB Output is correct
14 Correct 234 ms 31312 KB Output is correct
15 Correct 151 ms 24900 KB Output is correct
16 Correct 181 ms 24672 KB Output is correct
17 Correct 11 ms 8188 KB Output is correct
18 Correct 10 ms 8184 KB Output is correct
19 Correct 13 ms 8184 KB Output is correct
20 Correct 10 ms 8184 KB Output is correct
21 Correct 10 ms 8184 KB Output is correct
22 Correct 10 ms 8184 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8568 KB Output is correct
2 Correct 12 ms 8568 KB Output is correct
3 Correct 13 ms 8696 KB Output is correct
4 Correct 14 ms 8696 KB Output is correct
5 Correct 11 ms 8568 KB Output is correct
6 Correct 12 ms 8568 KB Output is correct
7 Correct 12 ms 8696 KB Output is correct
8 Correct 12 ms 8568 KB Output is correct
9 Correct 12 ms 8568 KB Output is correct
10 Correct 11 ms 8568 KB Output is correct
11 Correct 12 ms 8568 KB Output is correct
12 Correct 11 ms 8568 KB Output is correct
13 Correct 11 ms 8572 KB Output is correct
14 Correct 11 ms 8568 KB Output is correct
15 Correct 11 ms 8440 KB Output is correct
16 Correct 10 ms 8308 KB Output is correct
17 Correct 11 ms 8440 KB Output is correct
18 Correct 11 ms 8440 KB Output is correct
19 Correct 11 ms 8440 KB Output is correct
20 Correct 11 ms 8440 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 49960 KB Output is correct
2 Correct 400 ms 50008 KB Output is correct
3 Correct 374 ms 49868 KB Output is correct
4 Correct 447 ms 49916 KB Output is correct
5 Correct 379 ms 49820 KB Output is correct
6 Correct 460 ms 58296 KB Output is correct
7 Correct 428 ms 55496 KB Output is correct
8 Correct 426 ms 54256 KB Output is correct
9 Correct 409 ms 52728 KB Output is correct
10 Correct 377 ms 49952 KB Output is correct
11 Correct 379 ms 49844 KB Output is correct
12 Correct 380 ms 49844 KB Output is correct
13 Correct 371 ms 49848 KB Output is correct
14 Correct 346 ms 48160 KB Output is correct
15 Correct 296 ms 38636 KB Output is correct
16 Correct 165 ms 29888 KB Output is correct
17 Correct 242 ms 41748 KB Output is correct
18 Correct 248 ms 41556 KB Output is correct
19 Correct 279 ms 41388 KB Output is correct
20 Correct 291 ms 41500 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8568 KB Output is correct
2 Correct 12 ms 8568 KB Output is correct
3 Incorrect 14 ms 8540 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 50128 KB Output is correct
2 Correct 399 ms 49856 KB Output is correct
3 Incorrect 427 ms 48820 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8312 KB Output is correct
2 Correct 9 ms 8160 KB Output is correct
3 Correct 9 ms 8184 KB Output is correct
4 Correct 9 ms 8184 KB Output is correct
5 Correct 9 ms 8184 KB Output is correct
6 Correct 9 ms 8184 KB Output is correct
7 Incorrect 9 ms 8188 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8312 KB Output is correct
2 Correct 9 ms 8160 KB Output is correct
3 Correct 9 ms 8184 KB Output is correct
4 Correct 9 ms 8184 KB Output is correct
5 Correct 9 ms 8184 KB Output is correct
6 Correct 9 ms 8184 KB Output is correct
7 Incorrect 9 ms 8188 KB Output isn't correct
8 Halted 0 ms 0 KB -