oj.uz

Submission #55723

# Submission time Handle Problem Language Result Execution time Memory
55723 2018-07-08T16:48:29 Z mohammad_kilani Duathlon (APIO18_duathlon) C++17
31 / 100
 174 ms 23032 KB 
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define oo 1000000000
const int N = 100010;
int n , m , u , v , dfs_low[N] , dfs_num[N] , dfs_cnt = 0 , all[N], comp[N] , comp_cnt = 0;
vector< int > g[N] ; 
bool vis[N];
long long ans = 0 , A , B;

void DFS2(int node){
    vis[node] = true;
    comp[node] = comp_cnt;
    all[comp_cnt]++;
    for(int i=0;i<g[node].size();i++){
        if(!vis[g[node][i]])
            DFS2(g[node][i]);
    }
}

pair<int,pair<int,pair<long long,int> > > DFS(int node,int prnt){
    dfs_low[node] = dfs_num[node] = ++dfs_cnt;
    int num1 = 1 , num2 = 1 , num3 = all[comp[node]] - 1, num5 = 0;
    long long num4 = 0;
    pair<int,pair<int,pair<long long,int> > > tmp;
    for(int i=0;i<g[node].size();i++){
        if(g[node][i] == prnt) continue;
        if(dfs_num[g[node][i]] != 0){
            dfs_low[node] = min(dfs_low[node],dfs_num[g[node][i]]);
            continue;
        }
        tmp = DFS(g[node][i],node);
        num1 += tmp.first;
        dfs_low[node] = min(dfs_low[node],dfs_low[g[node][i]]);
        if(dfs_low[g[node][i]] == dfs_num[node]){
            num3 -= tmp.first;
            num4 += (long long)num5 * tmp.first;
            num5 += tmp.first;
            tmp.second.second.first += (long long)(all[comp[node]] - 1 - tmp.first) * tmp.second.second.second;
            ans += (long long)tmp.first * num3 * 2;
            ans += (long long)(tmp.second.first + 1) * tmp.second.first * (tmp.second.first - 1);
            ans += (long long)tmp.second.first * (tmp.second.first - 1) * (all[comp[node]] - tmp.second.first - 1) * 2;
            ans += (long long)(tmp.second.first - 1) * tmp.second.second.first * 2;
        }
        else if(dfs_low[g[node][i]] > dfs_num[node]){
            num4 += (long long)num5 * tmp.first;
            num5 += tmp.first;
            num3 -= tmp.first;
            ans += (long long)tmp.first * num3 * 2;
        }
        else{
            num2 += tmp.second.first;
            num4 += tmp.second.second.first;
            num4 += (long long)num5 * tmp.second.second.second;
            num5 += tmp.second.second.second;
        }
    }
    return make_pair(num1,make_pair(num2,make_pair(num4,num5)));
}



int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            DFS2(i);
            comp_cnt++;
        }
    }
    for(int i=1;i<=n;i++){
        if(dfs_num[i] == 0)
            DFS(i,-1);
    }
    cout << ans << endl;
    return 0;
}

Compilation message

count_triplets.cpp: In function 'void DFS2(int)':
count_triplets.cpp:15:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[node].size();i++){
                 ~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'std::pair<int, std::pair<int, std::pair<long long int, int> > > DFS(int, int)':
count_triplets.cpp:26:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[node].size();i++){
                 ~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:64: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:66: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 5 ms 2680 KB Output is correct
2 Correct 2 ms 2784 KB Output is correct
3 Correct 5 ms 2784 KB Output is correct
4 Correct 4 ms 2784 KB Output is correct
5 Correct 5 ms 2784 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 5 ms 2980 KB Output is correct
8 Correct 4 ms 2980 KB Output is correct
9 Correct 4 ms 2980 KB Output is correct
10 Correct 4 ms 2980 KB Output is correct
11 Correct 4 ms 2980 KB Output is correct
12 Correct 4 ms 2980 KB Output is correct
13 Correct 3 ms 2980 KB Output is correct
14 Correct 4 ms 2980 KB Output is correct
15 Correct 4 ms 2980 KB Output is correct
16 Correct 4 ms 2980 KB Output is correct
17 Correct 5 ms 2980 KB Output is correct
18 Correct 4 ms 2980 KB Output is correct
19 Correct 4 ms 2980 KB Output is correct
20 Correct 4 ms 2980 KB Output is correct
21 Correct 5 ms 2980 KB Output is correct
22 Incorrect 4 ms 2980 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 2 ms 2784 KB Output is correct
3 Correct 5 ms 2784 KB Output is correct
4 Correct 4 ms 2784 KB Output is correct
5 Correct 5 ms 2784 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 5 ms 2980 KB Output is correct
8 Correct 4 ms 2980 KB Output is correct
9 Correct 4 ms 2980 KB Output is correct
10 Correct 4 ms 2980 KB Output is correct
11 Correct 4 ms 2980 KB Output is correct
12 Correct 4 ms 2980 KB Output is correct
13 Correct 3 ms 2980 KB Output is correct
14 Correct 4 ms 2980 KB Output is correct
15 Correct 4 ms 2980 KB Output is correct
16 Correct 4 ms 2980 KB Output is correct
17 Correct 5 ms 2980 KB Output is correct
18 Correct 4 ms 2980 KB Output is correct
19 Correct 4 ms 2980 KB Output is correct
20 Correct 4 ms 2980 KB Output is correct
21 Correct 5 ms 2980 KB Output is correct
22 Incorrect 4 ms 2980 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 111 ms 22980 KB Output is correct
2 Correct 141 ms 23032 KB Output is correct
3 Correct 174 ms 23032 KB Output is correct
4 Correct 172 ms 23032 KB Output is correct
5 Correct 147 ms 23032 KB Output is correct
6 Correct 159 ms 23032 KB Output is correct
7 Correct 104 ms 23032 KB Output is correct
8 Correct 96 ms 23032 KB Output is correct
9 Correct 95 ms 23032 KB Output is correct
10 Correct 107 ms 23032 KB Output is correct
11 Correct 68 ms 23032 KB Output is correct
12 Correct 70 ms 23032 KB Output is correct
13 Correct 148 ms 23032 KB Output is correct
14 Correct 59 ms 23032 KB Output is correct
15 Correct 73 ms 23032 KB Output is correct
16 Correct 45 ms 23032 KB Output is correct
17 Correct 6 ms 23032 KB Output is correct
18 Correct 7 ms 23032 KB Output is correct
19 Correct 7 ms 23032 KB Output is correct
20 Correct 7 ms 23032 KB Output is correct
21 Correct 8 ms 23032 KB Output is correct
22 Correct 6 ms 23032 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 23032 KB Output is correct
2 Correct 119 ms 23032 KB Output is correct
3 Correct 135 ms 23032 KB Output is correct
4 Correct 133 ms 23032 KB Output is correct
5 Correct 122 ms 23032 KB Output is correct
6 Correct 150 ms 23032 KB Output is correct
7 Correct 138 ms 23032 KB Output is correct
8 Correct 136 ms 23032 KB Output is correct
9 Correct 135 ms 23032 KB Output is correct
10 Correct 76 ms 23032 KB Output is correct
11 Correct 80 ms 23032 KB Output is correct
12 Correct 77 ms 23032 KB Output is correct
13 Correct 129 ms 23032 KB Output is correct
14 Correct 70 ms 23032 KB Output is correct
15 Correct 65 ms 23032 KB Output is correct
16 Correct 45 ms 23032 KB Output is correct
17 Correct 55 ms 23032 KB Output is correct
18 Correct 60 ms 23032 KB Output is correct
19 Correct 56 ms 23032 KB Output is correct
20 Correct 86 ms 23032 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 23032 KB Output is correct
2 Correct 126 ms 23032 KB Output is correct
3 Incorrect 122 ms 23032 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 2 ms 2784 KB Output is correct
3 Correct 5 ms 2784 KB Output is correct
4 Correct 4 ms 2784 KB Output is correct
5 Correct 5 ms 2784 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 5 ms 2980 KB Output is correct
8 Correct 4 ms 2980 KB Output is correct
9 Correct 4 ms 2980 KB Output is correct
10 Correct 4 ms 2980 KB Output is correct
11 Correct 4 ms 2980 KB Output is correct
12 Correct 4 ms 2980 KB Output is correct
13 Correct 3 ms 2980 KB Output is correct
14 Correct 4 ms 2980 KB Output is correct
15 Correct 4 ms 2980 KB Output is correct
16 Correct 4 ms 2980 KB Output is correct
17 Correct 5 ms 2980 KB Output is correct
18 Correct 4 ms 2980 KB Output is correct
19 Correct 4 ms 2980 KB Output is correct
20 Correct 4 ms 2980 KB Output is correct
21 Correct 5 ms 2980 KB Output is correct
22 Incorrect 4 ms 2980 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 2 ms 2784 KB Output is correct
3 Correct 5 ms 2784 KB Output is correct
4 Correct 4 ms 2784 KB Output is correct
5 Correct 5 ms 2784 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 5 ms 2980 KB Output is correct
8 Correct 4 ms 2980 KB Output is correct
9 Correct 4 ms 2980 KB Output is correct
10 Correct 4 ms 2980 KB Output is correct
11 Correct 4 ms 2980 KB Output is correct
12 Correct 4 ms 2980 KB Output is correct
13 Correct 3 ms 2980 KB Output is correct
14 Correct 4 ms 2980 KB Output is correct
15 Correct 4 ms 2980 KB Output is correct
16 Correct 4 ms 2980 KB Output is correct
17 Correct 5 ms 2980 KB Output is correct
18 Correct 4 ms 2980 KB Output is correct
19 Correct 4 ms 2980 KB Output is correct
20 Correct 4 ms 2980 KB Output is correct
21 Correct 5 ms 2980 KB Output is correct
22 Incorrect 4 ms 2980 KB Output isn't correct
23 Halted 0 ms 0 KB -