답안 #48873 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48873	2018-05-19T11:43:40 Z	IvanC	철인 이종 경기 (APIO18_duathlon)	C++17	31 / 100	303 ms	22380 KB

count_triplets

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> ii;
 
const int MAXN = 1e5 + 10;
 
 
vector<int> grafo[MAXN],tree[MAXN];
vector<ii> pontes;
int block[MAXN],grau[MAXN],sz[MAXN],N,M,dsu_p[MAXN],dsu_tam[MAXN],num[MAXN],low[MAXN],dfsPtr;
ll tot,comp_size;
 
int find(int x){
    if(x == dsu_p[x]) return x;
    return dsu_p[x] = find(dsu_p[x]);
}
 
void join(int x,int y){
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(dsu_tam[x] < dsu_tam[y]) swap(x,y);
    dsu_tam[x] += dsu_tam[y];
    dsu_p[y] = x;
}
 
void dfs_bridge(int v,int p){
    num[v] = low[v] = ++dfsPtr;
    for(int u : grafo[v]){
        if(u == p) continue;
        if(num[u] == 0){
            dfs_bridge(u,v);
            if(low[u] > num[v]){
                pontes.push_back(ii(u,v));
            }
            else{
                join(u,v);
            }
            low[v] = min(low[v],low[u]);
        }
        else{
            low[v] = min(low[v],num[u]);
        }
    }
}
 
void dfs_tree_1(int v,int p){
    block[v] = 1;
    sz[v] = dsu_tam[v];
    for(int u : tree[v]){
        if(u == p) continue;
        dfs_tree_1(u,v);
        sz[v] += sz[u];
    }
}
 
void dfs_tree_2(int v,int p){
    tot += 1LL*(dsu_tam[v])*(dsu_tam[v] - 1)*(dsu_tam[v]-2);
    vector<int> filhos;
    for(int u : tree[v]){
        if(u == p) continue;
        filhos.push_back(sz[u]);
        dfs_tree_2(u,v);
    }
    filhos.push_back(comp_size - sz[v]);
    for(int i = 0;i<filhos.size();i++){
        int sub_arvore = filhos[i];
        tot += 1LL*dsu_tam[v]*sub_arvore*(comp_size - sub_arvore - dsu_tam[v]);
        tot += 2LL*sub_arvore*(dsu_tam[v] - 1)*(dsu_tam[v] - 2);
        tot += 2LL*sub_arvore*(dsu_tam[v] - 1);
    }
}
 
int main(){
    scanf("%d %d",&N,&M);
     
    for(int i = 1;i<=N;i++){
        dsu_p[i] = i;
        dsu_tam[i] = 1;
    }
 
    for(int i = 1;i<=M;i++){
        int u,v;
        scanf("%d %d",&u,&v);
        grafo[v].push_back(u);
        grafo[u].push_back(v);
    }
 
    for(int i = 1;i<=N;i++){
        if(num[i] == 0) dfs_bridge(i,-1);
    }
 
    for(int i = 0;i<pontes.size();i++){
        int u = find(pontes[i].first);
        int v = find(pontes[i].second);
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
 
    //printf("Pontes %d\n",(int)pontes.size());
 
    for(int i = 1;i<=N;i++){
        if(find(i) != i || block[i]) continue;
        dfs_tree_1(i,-1);
        comp_size = sz[i];
        dfs_tree_2(i,-1);
    }
 
    printf("%lld\n",tot);
 
    return 0;
}

Compilation message

count_triplets.cpp: In function 'void dfs_tree_2(int, int)':
count_triplets.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<filhos.size();i++){
                   ~^~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:95:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<pontes.size();i++){
                   ~^~~~~~~~~~~~~~
count_triplets.cpp:77: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:86: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

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	4984 KB	Output is correct
2	Correct	5 ms	5096 KB	Output is correct
3	Correct	6 ms	5172 KB	Output is correct
4	Correct	5 ms	5228 KB	Output is correct
5	Correct	6 ms	5228 KB	Output is correct
6	Correct	6 ms	5228 KB	Output is correct
7	Incorrect	6 ms	5228 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	4984 KB	Output is correct
2	Correct	5 ms	5096 KB	Output is correct
3	Correct	6 ms	5172 KB	Output is correct
4	Correct	5 ms	5228 KB	Output is correct
5	Correct	6 ms	5228 KB	Output is correct
6	Correct	6 ms	5228 KB	Output is correct
7	Incorrect	6 ms	5228 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #3
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	159 ms	19356 KB	Output is correct
2	Correct	123 ms	19412 KB	Output is correct
3	Correct	165 ms	19412 KB	Output is correct
4	Correct	137 ms	19412 KB	Output is correct
5	Correct	131 ms	19412 KB	Output is correct
6	Correct	152 ms	19412 KB	Output is correct
7	Correct	159 ms	19412 KB	Output is correct
8	Correct	170 ms	19412 KB	Output is correct
9	Correct	139 ms	19412 KB	Output is correct
10	Correct	150 ms	19412 KB	Output is correct
11	Correct	124 ms	19412 KB	Output is correct
12	Correct	109 ms	19412 KB	Output is correct
13	Correct	107 ms	19412 KB	Output is correct
14	Correct	113 ms	19412 KB	Output is correct
15	Correct	91 ms	19412 KB	Output is correct
16	Correct	106 ms	19412 KB	Output is correct
17	Correct	16 ms	19412 KB	Output is correct
18	Correct	15 ms	19412 KB	Output is correct
19	Correct	17 ms	19412 KB	Output is correct
20	Correct	16 ms	19412 KB	Output is correct
21	Correct	16 ms	19412 KB	Output is correct
22	Correct	23 ms	19412 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	19412 KB	Output is correct
2	Correct	8 ms	19412 KB	Output is correct
3	Correct	8 ms	19412 KB	Output is correct
4	Correct	10 ms	19412 KB	Output is correct
5	Correct	6 ms	19412 KB	Output is correct
6	Correct	8 ms	19412 KB	Output is correct
7	Correct	8 ms	19412 KB	Output is correct
8	Correct	7 ms	19412 KB	Output is correct
9	Correct	8 ms	19412 KB	Output is correct
10	Correct	8 ms	19412 KB	Output is correct
11	Correct	7 ms	19412 KB	Output is correct
12	Correct	8 ms	19412 KB	Output is correct
13	Correct	8 ms	19412 KB	Output is correct
14	Correct	7 ms	19412 KB	Output is correct
15	Correct	7 ms	19412 KB	Output is correct
16	Correct	8 ms	19412 KB	Output is correct
17	Correct	7 ms	19412 KB	Output is correct
18	Correct	9 ms	19412 KB	Output is correct
19	Correct	32 ms	19412 KB	Output is correct
20	Correct	6 ms	19412 KB	Output is correct

Subtask #5
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	192 ms	19412 KB	Output is correct
2	Correct	191 ms	19412 KB	Output is correct
3	Correct	183 ms	19412 KB	Output is correct
4	Correct	194 ms	19412 KB	Output is correct
5	Correct	190 ms	19412 KB	Output is correct
6	Correct	247 ms	22380 KB	Output is correct
7	Correct	211 ms	22380 KB	Output is correct
8	Correct	204 ms	22380 KB	Output is correct
9	Correct	193 ms	22380 KB	Output is correct
10	Correct	153 ms	22380 KB	Output is correct
11	Correct	135 ms	22380 KB	Output is correct
12	Correct	303 ms	22380 KB	Output is correct
13	Correct	138 ms	22380 KB	Output is correct
14	Correct	121 ms	22380 KB	Output is correct
15	Correct	147 ms	22380 KB	Output is correct
16	Correct	98 ms	22380 KB	Output is correct
17	Correct	120 ms	22380 KB	Output is correct
18	Correct	120 ms	22380 KB	Output is correct
19	Correct	136 ms	22380 KB	Output is correct
20	Correct	118 ms	22380 KB	Output is correct

Subtask #6
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	22380 KB	Output is correct
2	Correct	7 ms	22380 KB	Output is correct
3	Incorrect	7 ms	22380 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	135 ms	22380 KB	Output is correct
2	Correct	162 ms	22380 KB	Output is correct
3	Incorrect	113 ms	22380 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	4984 KB	Output is correct
2	Correct	5 ms	5096 KB	Output is correct
3	Correct	6 ms	5172 KB	Output is correct
4	Correct	5 ms	5228 KB	Output is correct
5	Correct	6 ms	5228 KB	Output is correct
6	Correct	6 ms	5228 KB	Output is correct
7	Incorrect	6 ms	5228 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	4984 KB	Output is correct
2	Correct	5 ms	5096 KB	Output is correct
3	Correct	6 ms	5172 KB	Output is correct
4	Correct	5 ms	5228 KB	Output is correct
5	Correct	6 ms	5228 KB	Output is correct
6	Correct	6 ms	5228 KB	Output is correct
7	Incorrect	6 ms	5228 KB	Output isn't correct
8	Halted	0 ms	0 KB	-