oj.uz

Submission #132990

# Submission time Handle Problem Language Result Execution time Memory
132990 2019-07-20T03:34:49 Z ae04071 Duathlon (APIO18_duathlon) C++11
31 / 100
 168 ms 27640 KB 
#include <bits/stdc++.h>
using namespace std;

int n,m,cut[100001],dfn[100001],low[100001],o,dn;
int bsz[200001];
vector<int> adj[100001],badj[200001];
stack<int> stk;

int ts;
void addEdge(int u,int v) {
    badj[u].push_back(v);
    badj[v].push_back(u);
}
void dfs(int cur,int p) {
    ts++;
    dfn[cur] = low[cur] = ++dn;
    stk.push(cur);
    for(auto &it:adj[cur]) if(it!=p) {
        if(dfn[it]) low[cur] = min(low[cur],dfn[it]);
        else {
            dfs(it,cur);
            low[cur] = min(low[cur],low[it]);
            if(low[it]>=dfn[cur]) {
                ++n;
                cut[cur] = 1;
                while(!stk.empty()) {
                    int v=stk.top();
                    bsz[n]++;
                    if(cut[v]) addEdge(n, v);
                    if(v==cur) break;
                    stk.pop();
                }
            }
        }
    }
}

long long ans;
int sz[200001];
int cal_dfs(int cur,int p) {
    sz[cur] = bsz[cur];
    for(auto &it:badj[cur]) if(it!=p) sz[cur] += cal_dfs(it,cur);
    sz[cur] -= ((int)badj[cur].size() - (p>0) - (cur<=o));

    if(cur>o) {
        for(auto &it:badj[cur]) if(it!=p) ans += 1ll*(bsz[cur]-1)*sz[it]*(sz[it]-1);
        ans += 1ll*(bsz[cur]-1)*(ts-sz[cur]+1)*(ts-sz[cur]);
    }
    return sz[cur];
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i=0,u,v;i<m;i++) {
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    o = n;

    long long ret = 0;
    for(int i=1;i<=o;i++) if(!dfn[i]) {
        ts=0; ans=0;
        dfs(i,0);
        while(!stk.empty()) stk.pop();
        
        cal_dfs(i, 0);
        ret += 1ll*ts*(ts-1)*(ts-2) - ans;
    }
    printf("%lld\n",ret);
    
    return 0;
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
count_triplets.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&u,&v);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Incorrect 8 ms 7416 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 100 ms 21112 KB Output is correct
2 Correct 89 ms 21072 KB Output is correct
3 Correct 146 ms 22116 KB Output is correct
4 Correct 109 ms 21240 KB Output is correct
5 Correct 110 ms 18552 KB Output is correct
6 Correct 135 ms 21276 KB Output is correct
7 Correct 128 ms 19376 KB Output is correct
8 Correct 123 ms 19920 KB Output is correct
9 Correct 116 ms 17912 KB Output is correct
10 Correct 112 ms 17848 KB Output is correct
11 Correct 93 ms 15324 KB Output is correct
12 Correct 91 ms 15224 KB Output is correct
13 Correct 84 ms 15224 KB Output is correct
14 Correct 79 ms 14968 KB Output is correct
15 Correct 64 ms 14328 KB Output is correct
16 Correct 65 ms 14096 KB Output is correct
17 Correct 14 ms 8824 KB Output is correct
18 Correct 12 ms 8952 KB Output is correct
19 Correct 12 ms 8824 KB Output is correct
20 Correct 13 ms 8824 KB Output is correct
21 Correct 13 ms 8824 KB Output is correct
22 Correct 11 ms 8824 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 17804 KB Output is correct
2 Correct 134 ms 17760 KB Output is correct
3 Correct 132 ms 17756 KB Output is correct
4 Correct 131 ms 17760 KB Output is correct
5 Correct 130 ms 17712 KB Output is correct
6 Correct 168 ms 27640 KB Output is correct
7 Correct 161 ms 24056 KB Output is correct
8 Correct 148 ms 22476 KB Output is correct
9 Correct 145 ms 20964 KB Output is correct
10 Correct 127 ms 17820 KB Output is correct
11 Correct 129 ms 17784 KB Output is correct
12 Correct 126 ms 17784 KB Output is correct
13 Correct 125 ms 17784 KB Output is correct
14 Correct 113 ms 17272 KB Output is correct
15 Correct 97 ms 16764 KB Output is correct
16 Correct 63 ms 14460 KB Output is correct
17 Correct 74 ms 15984 KB Output is correct
18 Correct 75 ms 15984 KB Output is correct
19 Correct 109 ms 16112 KB Output is correct
20 Correct 114 ms 16032 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Incorrect 9 ms 7544 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 17784 KB Output is correct
2 Correct 138 ms 18040 KB Output is correct
3 Incorrect 151 ms 17272 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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