oj.uz

답안 #131112

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
131112 2019-07-16T13:40:49 Z oolimry 철인 이종 경기 (APIO18_duathlon) C++14
31 / 100
 465 ms 57012 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 + extra);

            ///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] - 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++){
                       ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 9 ms 8184 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 8156 KB Output is correct
7 Correct 9 ms 8184 KB Output is correct
8 Incorrect 9 ms 8184 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 9 ms 8184 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 8156 KB Output is correct
7 Correct 9 ms 8184 KB Output is correct
8 Incorrect 9 ms 8184 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 222 ms 32320 KB Output is correct
2 Correct 276 ms 32388 KB Output is correct
3 Correct 338 ms 40272 KB Output is correct
4 Correct 290 ms 36424 KB Output is correct
5 Correct 304 ms 36100 KB Output is correct
6 Correct 360 ms 39664 KB Output is correct
7 Correct 368 ms 39132 KB Output is correct
8 Correct 360 ms 40260 KB Output is correct
9 Correct 365 ms 37592 KB Output is correct
10 Correct 337 ms 35736 KB Output is correct
11 Correct 250 ms 31428 KB Output is correct
12 Correct 239 ms 31176 KB Output is correct
13 Correct 217 ms 30804 KB Output is correct
14 Correct 214 ms 30532 KB Output is correct
15 Correct 161 ms 24284 KB Output is correct
16 Correct 159 ms 23872 KB Output is correct
17 Correct 10 ms 8184 KB Output is correct
18 Correct 10 ms 8184 KB Output is correct
19 Correct 10 ms 8156 KB Output is correct
20 Correct 11 ms 8184 KB Output is correct
21 Correct 10 ms 8184 KB Output is correct
22 Correct 10 ms 8188 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 8568 KB Output is correct
2 Correct 12 ms 8568 KB Output is correct
3 Correct 12 ms 8744 KB Output is correct
4 Correct 12 ms 8696 KB Output is correct
5 Correct 11 ms 8632 KB Output is correct
6 Correct 11 ms 8568 KB Output is correct
7 Correct 12 ms 8696 KB Output is correct
8 Correct 11 ms 8568 KB Output is correct
9 Correct 11 ms 8568 KB Output is correct
10 Correct 11 ms 8568 KB Output is correct
11 Correct 11 ms 8572 KB Output is correct
12 Correct 11 ms 8568 KB Output is correct
13 Correct 12 ms 8568 KB Output is correct
14 Correct 12 ms 8480 KB Output is correct
15 Correct 11 ms 8440 KB Output is correct
16 Correct 10 ms 8312 KB Output is correct
17 Correct 11 ms 8568 KB Output is correct
18 Correct 11 ms 8440 KB Output is correct
19 Correct 11 ms 8440 KB Output is correct
20 Correct 10 ms 8440 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 384 ms 48588 KB Output is correct
2 Correct 387 ms 48760 KB Output is correct
3 Correct 384 ms 48696 KB Output is correct
4 Correct 383 ms 48720 KB Output is correct
5 Correct 381 ms 48696 KB Output is correct
6 Correct 465 ms 57012 KB Output is correct
7 Correct 428 ms 54216 KB Output is correct
8 Correct 434 ms 52916 KB Output is correct
9 Correct 415 ms 51384 KB Output is correct
10 Correct 394 ms 48636 KB Output is correct
11 Correct 382 ms 48568 KB Output is correct
12 Correct 383 ms 48568 KB Output is correct
13 Correct 375 ms 48664 KB Output is correct
14 Correct 340 ms 47032 KB Output is correct
15 Correct 301 ms 37696 KB Output is correct
16 Correct 189 ms 29320 KB Output is correct
17 Correct 270 ms 40472 KB Output is correct
18 Correct 246 ms 40244 KB Output is correct
19 Correct 248 ms 40244 KB Output is correct
20 Correct 269 ms 40184 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 8568 KB Output is correct
2 Correct 19 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

# 결과 실행 시간 메모리 Grader output
1 Correct 386 ms 48632 KB Output is correct
2 Correct 398 ms 48728 KB Output is correct
3 Incorrect 407 ms 47396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 9 ms 8184 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 8156 KB Output is correct
7 Correct 9 ms 8184 KB Output is correct
8 Incorrect 9 ms 8184 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 9 ms 8184 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 8156 KB Output is correct
7 Correct 9 ms 8184 KB Output is correct
8 Incorrect 9 ms 8184 KB Output isn't correct
9 Halted 0 ms 0 KB -