Submission #829648

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
829648	2023-08-18T13:46:52 Z	FatihSolak	Duathlon (APIO18_duathlon)	C++17	31 / 100	81 ms	26092 KB

count_triplets

#include <bits/stdc++.h>
#define N 100005
using namespace std;
vector<int> adj[N];
vector<int> adj2[N];
vector<int> adj3[N];
int d[N];
int low[N];
vector<pair<int,int>> edges;
int totsize[N];
int val = 0;
void dfs(int v,int par){
    d[v] = d[par] + 1;
    low[v] = d[v];
    totsize[v] = 1;
    for(auto u:adj[v]){
        if(u == par)
            continue;
        if(d[u] != 0){
            low[v] = min(d[u],low[v]);
            if(d[v] < d[u]){
                adj2[v].push_back(u);
                adj2[u].push_back(v);
            }
        }
        else{
            dfs(u,v);
            totsize[v] += totsize[u];
            low[v] = min(low[v],low[u]);
            if(low[u] <= d[v]){
                adj2[v].push_back(u);
                adj2[u].push_back(v);
            }
            else{
                edges.push_back({u,v});
            }
        }
    }
}
int cnt[N];
int group[N];
int sub[N];
int n;
long long ans = 0;
void dfs2(int v){
    cnt[group[v]]++;
    for(auto u:adj2[v]){
        if(group[u])continue;
        group[u] = group[v];
        dfs2(u);
    }
}
void dfs3(int v,int par){
    sub[v] = cnt[v];
    for(auto u:adj3[v]){
        if(u == par)
            continue;
        dfs3(u,v);
        sub[v] += sub[u];
    }
    ans += 2 * (long long)cnt[v] * (cnt[v] - 1) * (val - cnt[v]);
    ans -= 2 * (long long)(cnt[v] - 1) * (val - cnt[v]);
    for(auto u:adj3[v]){
        if(u == par){
            ans += (long long)cnt[v] * (val - sub[v]) * (sub[v] - cnt[v]);
        }
        else{
            ans += (long long)cnt[v] * (val - sub[u] - cnt[v]) * (sub[u]);
        }
    }
}
void solve(){
    int m;
    cin >> n >> m;
    for(int i = 1;i<=m;i++){
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i = 1;i<=n;i++){
        if(d[i] == 0)
            dfs(i,0);
    }
    for(int i = 1;i<=n;i++){
        if(group[i] == 0){
            group[i] = i;
            dfs2(i);
            ans += (long long)cnt[i] * (cnt[i]-1) * (cnt[i]-2);
        }
    }
    for(auto u:edges){
        adj3[group[u.first]].push_back(group[u.second]);
        adj3[group[u.second]].push_back(group[u.first]);
    }
    for(int i = 1;i<=n;i++){
        if(sub[i] == 0 && group[i] == i){
            val = totsize[i];
            dfs3(i,0);
            assert(val == sub[i]);
        }
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local    
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	7380 KB	Output is correct
2	Correct	3 ms	7380 KB	Output is correct
3	Correct	4 ms	7380 KB	Output is correct
4	Correct	3 ms	7380 KB	Output is correct
5	Correct	3 ms	7380 KB	Output is correct
6	Correct	3 ms	7380 KB	Output is correct
7	Incorrect	4 ms	7380 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	81 ms	26028 KB	Output is correct
2	Correct	56 ms	26092 KB	Output is correct
3	Correct	81 ms	21772 KB	Output is correct
4	Correct	63 ms	24364 KB	Output is correct
5	Correct	59 ms	19828 KB	Output is correct
6	Correct	73 ms	19968 KB	Output is correct
7	Correct	77 ms	18596 KB	Output is correct
8	Correct	77 ms	19416 KB	Output is correct
9	Correct	60 ms	17512 KB	Output is correct
10	Correct	50 ms	18372 KB	Output is correct
11	Correct	77 ms	16168 KB	Output is correct
12	Correct	66 ms	15908 KB	Output is correct
13	Correct	47 ms	15972 KB	Output is correct
14	Correct	39 ms	15692 KB	Output is correct
15	Correct	31 ms	15072 KB	Output is correct
16	Correct	34 ms	14820 KB	Output is correct
17	Correct	7 ms	9684 KB	Output is correct
18	Correct	6 ms	9684 KB	Output is correct
19	Correct	7 ms	9724 KB	Output is correct
20	Correct	7 ms	9704 KB	Output is correct
21	Correct	8 ms	9684 KB	Output is correct
22	Correct	6 ms	9684 KB	Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	49 ms	16948 KB	Output is correct
2	Correct	48 ms	16976 KB	Output is correct
3	Correct	44 ms	16852 KB	Output is correct
4	Correct	48 ms	16960 KB	Output is correct
5	Correct	47 ms	16952 KB	Output is correct
6	Correct	54 ms	22668 KB	Output is correct
7	Correct	51 ms	20672 KB	Output is correct
8	Correct	55 ms	19648 KB	Output is correct
9	Correct	59 ms	18752 KB	Output is correct
10	Correct	62 ms	16852 KB	Output is correct
11	Correct	49 ms	16936 KB	Output is correct
12	Correct	56 ms	17096 KB	Output is correct
13	Correct	44 ms	16936 KB	Output is correct
14	Correct	41 ms	16716 KB	Output is correct
15	Correct	38 ms	16332 KB	Output is correct
16	Correct	27 ms	14732 KB	Output is correct
17	Correct	36 ms	17520 KB	Output is correct
18	Correct	36 ms	17464 KB	Output is correct
19	Correct	48 ms	17664 KB	Output is correct
20	Correct	42 ms	17472 KB	Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	16952 KB	Output is correct
2	Correct	46 ms	16840 KB	Output is correct
3	Incorrect	59 ms	17048 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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

Submission #829648

Compilation message