oj.uz

Submission #132984

# Submission time Handle Problem Language Result Execution time Memory
132984 2019-07-20T03:26:34 Z ae04071 Duathlon (APIO18_duathlon) C++11
31 / 100
 162 ms 27896 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],low[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 92 ms 21084 KB Output is correct
2 Correct 97 ms 21052 KB Output is correct
3 Correct 130 ms 22008 KB Output is correct
4 Correct 114 ms 21368 KB Output is correct
5 Correct 116 ms 18680 KB Output is correct
6 Correct 129 ms 21304 KB Output is correct
7 Correct 123 ms 19448 KB Output is correct
8 Correct 126 ms 20088 KB Output is correct
9 Correct 128 ms 18168 KB Output is correct
10 Correct 119 ms 17844 KB Output is correct
11 Correct 97 ms 15480 KB Output is correct
12 Correct 113 ms 15352 KB Output is correct
13 Correct 88 ms 15352 KB Output is correct
14 Correct 89 ms 15096 KB Output is correct
15 Correct 66 ms 14460 KB Output is correct
16 Correct 64 ms 14132 KB Output is correct
17 Correct 11 ms 8952 KB Output is correct
18 Correct 11 ms 8824 KB Output is correct
19 Correct 11 ms 8824 KB Output is correct
20 Correct 11 ms 8824 KB Output is correct
21 Correct 11 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 10 ms 7544 KB Output is correct
2 Correct 9 ms 7544 KB Output is correct
3 Correct 9 ms 7544 KB Output is correct
4 Correct 9 ms 7672 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 7672 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 7544 KB Output is correct
14 Correct 9 ms 7416 KB Output is correct
15 Correct 9 ms 7428 KB Output is correct
16 Correct 9 ms 7492 KB Output is correct
17 Correct 9 ms 7416 KB Output is correct
18 Correct 9 ms 7544 KB Output is correct
19 Correct 21 ms 7544 KB Output is correct
20 Correct 11 ms 7544 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 17784 KB Output is correct
2 Correct 126 ms 17912 KB Output is correct
3 Correct 121 ms 17912 KB Output is correct
4 Correct 126 ms 17912 KB Output is correct
5 Correct 125 ms 18040 KB Output is correct
6 Correct 159 ms 27896 KB Output is correct
7 Correct 162 ms 24088 KB Output is correct
8 Correct 144 ms 22520 KB Output is correct
9 Correct 144 ms 21016 KB Output is correct
10 Correct 126 ms 17884 KB Output is correct
11 Correct 128 ms 17820 KB Output is correct
12 Correct 125 ms 17912 KB Output is correct
13 Correct 128 ms 17876 KB Output is correct
14 Correct 108 ms 17400 KB Output is correct
15 Correct 94 ms 16988 KB Output is correct
16 Correct 63 ms 14584 KB Output is correct
17 Correct 74 ms 16092 KB Output is correct
18 Correct 77 ms 16112 KB Output is correct
19 Correct 79 ms 16316 KB Output is correct
20 Correct 86 ms 16248 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 17912 KB Output is correct
2 Correct 139 ms 18216 KB Output is correct
3 Incorrect 141 ms 17276 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 -