oj.uz

Submission #49593

# Submission time Handle Problem Language Result Execution time Memory
49593 2018-05-31T20:49:06 Z mohammad_kilani Duathlon (APIO18_duathlon) C++17
18 / 100
 1000 ms 19488 KB 
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define oo 200000000
const int N = 100010;
const int M = 100010;
int n , m ,comp[N] , num[N] , comp_cnt = 0 , u , v  , dfs_cnt = 0 , dfs_low[N] , dfs_num[N] , num1[N] , num2[N] , tmp[N] , num3[N] , tmp2[N] , s = 0;
bool vis[N] ; 
long long all = 0 , ans = 0, all2 = 0;
vector< int > g[N] ; 

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

void DFS(int node, int prnt){
    dfs_low[node] = dfs_num[node] = dfs_cnt++;
    num1[node] = 1;
    num2[node] = 1;
    tmp[node] = num[comp[node]] - 1;
    int s = num[comp[node]] - 1;
    vis[node] = true;
    vector< int > v;
    for(int i=0;i<g[node].size();i++){
        if(g[node][i] == prnt) continue;
        if(vis[g[node][i]]){
            dfs_low[node] = min(dfs_low[node],dfs_num[g[node][i]]);
            continue;
        }
        DFS(g[node][i],node);
        dfs_low[node] = min(dfs_low[node],dfs_low[g[node][i]]);
        num1[node] += num1[g[node][i]];
        if(dfs_low[g[node][i]] == dfs_num[node]){
            ans += (long long)num2[g[node][i]] * (num2[g[node][i]] + 1) * (num2[g[node][i]] - 1);
            all -= (long long)num2[g[node][i]] * (num2[g[node][i]] + 1) * (num2[g[node][i]] - 1) / 6;
            tmp[node] -= num1[g[node][i]];
            s -= num1[g[node][i]];
            ans += (long long)tmp[node] * num1[g[node][i]] * 2;
            all -= (long long)tmp[node] * num1[g[node][i]];
            v.push_back(num1[g[node][i]]);
        }   
        else if(dfs_low[g[node][i]] < dfs_num[node]){
            num2[node] += num2[g[node][i]];
        }
        else{
            v.push_back(num1[g[node][i]]);
            s -= num1[g[node][i]];
            tmp[node] -= num1[g[node][i]];
            ans += (long long)tmp[node] * num1[g[node][i]] * 2;
            all -= (long long)tmp[node] * num1[g[node][i]];
        }
    }
    v.push_back(s);
    for(int i=0;i<v.size();i++){
        for(int j=i+1;j<v.size();j++){
            for(int k=j+1;k<v.size();k++){
                all -= (long long)v[i] * v[j] * v[k];
            }
        }
    }
}

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] == false){
            DFS1(i);
            all += (long long)num[comp_cnt] * (num[comp_cnt] - 1) * (num[comp_cnt] - 2) / 6;
            comp_cnt++;
        }
    }
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
        if(vis[i] == false)
            DFS(i,-1);
    }
    ans += (long long)all * 4;
    cout << ans << endl;
    return 0;
}

Compilation message

count_triplets.cpp: In function 'void DFS1(int)':
count_triplets.cpp:16: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 'void DFS(int, int)':
count_triplets.cpp:30:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[node].size();i++){
                 ~^~~~~~~~~~~~~~~
count_triplets.cpp:60:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v.size();i++){
                 ~^~~~~~~~~
count_triplets.cpp:61:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=i+1;j<v.size();j++){
                       ~^~~~~~~~~
count_triplets.cpp:62:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k=j+1;k<v.size();k++){
                           ~^~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:70: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:72: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 4 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2824 KB Output is correct
4 Correct 4 ms 2840 KB Output is correct
5 Correct 5 ms 2840 KB Output is correct
6 Correct 3 ms 2888 KB Output is correct
7 Incorrect 4 ms 2948 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2824 KB Output is correct
4 Correct 4 ms 2840 KB Output is correct
5 Correct 5 ms 2840 KB Output is correct
6 Correct 3 ms 2888 KB Output is correct
7 Incorrect 4 ms 2948 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 146 ms 19488 KB Output is correct
2 Correct 140 ms 19488 KB Output is correct
3 Correct 159 ms 19488 KB Output is correct
4 Correct 128 ms 19488 KB Output is correct
5 Correct 123 ms 19488 KB Output is correct
6 Correct 160 ms 19488 KB Output is correct
7 Correct 122 ms 19488 KB Output is correct
8 Correct 165 ms 19488 KB Output is correct
9 Correct 109 ms 19488 KB Output is correct
10 Correct 109 ms 19488 KB Output is correct
11 Correct 92 ms 19488 KB Output is correct
12 Correct 99 ms 19488 KB Output is correct
13 Correct 90 ms 19488 KB Output is correct
14 Correct 77 ms 19488 KB Output is correct
15 Correct 58 ms 19488 KB Output is correct
16 Correct 64 ms 19488 KB Output is correct
17 Correct 12 ms 19488 KB Output is correct
18 Correct 11 ms 19488 KB Output is correct
19 Correct 12 ms 19488 KB Output is correct
20 Correct 13 ms 19488 KB Output is correct
21 Correct 12 ms 19488 KB Output is correct
22 Correct 13 ms 19488 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 19488 KB Output is correct
2 Correct 126 ms 19488 KB Output is correct
3 Correct 158 ms 19488 KB Output is correct
4 Correct 131 ms 19488 KB Output is correct
5 Correct 118 ms 19488 KB Output is correct
6 Correct 152 ms 19488 KB Output is correct
7 Correct 155 ms 19488 KB Output is correct
8 Correct 150 ms 19488 KB Output is correct
9 Correct 124 ms 19488 KB Output is correct
10 Correct 97 ms 19488 KB Output is correct
11 Correct 101 ms 19488 KB Output is correct
12 Correct 120 ms 19488 KB Output is correct
13 Correct 99 ms 19488 KB Output is correct
14 Correct 95 ms 19488 KB Output is correct
15 Correct 87 ms 19488 KB Output is correct
16 Correct 58 ms 19488 KB Output is correct
17 Execution timed out 1079 ms 19488 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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