답안 #321285

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
321285	2020-11-11T22:34:09 Z	couplefire	철인 이종 경기 (APIO18_duathlon)	C++17	0 / 100	168 ms	37732 KB

count_triplets

#include <bits/stdc++.h>
using namespace std;
#define MAXN 200015

int low[MAXN], tin[MAXN], curTime = 0, curComp = 0;
vector<int> tree[MAXN], children[MAXN];
bool isCut[MAXN];
vector<int> adj[MAXN];
bool visited[MAXN];
int n, m;
int nn = 0;
long long ans = 0;

void tarjan(int v, int p){
    visited[v] = 1;
    tin[v] = curTime++;
    low[v] = curTime-1;
    nn++;
    for(auto u : adj[v]){
        if(u == p) continue;
        if(visited[u]){
            low[v] = min(low[v], tin[u]);
        }
        else{
            children[v].push_back(u);
            tarjan(u, v);
            low[v] = min(low[v], low[u]);
            if(low[u] >= tin[v]){
                isCut[u] = 1;
            }
        }
    }
}

void ae(int a, int b){
    tree[a].push_back(b);
    tree[b].push_back(a);
}

void gen(int v, int b){
    if(b != 0) ae(v, b);
    for(auto u : children[v]){
        if(isCut[u]){
            curComp++;
            ae(v, curComp);
            gen(u, curComp);
        }
        else{
            gen(u, b);
        }
    }
}

int getSiz(int v, int p){
    if(v < n){
        int aa = 0;
        for(auto u : tree[v]){
            if(u == p) continue;
            aa += getSiz(u, v)-1;
        }
        return aa+1;
    }
    int bb = tree[v].size();
    int aa = 0;
    for(auto u : tree[v]){
        if(u == p) continue;
        if(tree[u].size() == 1) continue;
        aa += getSiz(u, v);
        bb--;
    }
    ans -= 1ll*bb*aa*(aa-1);
    ans += 1ll*bb*(tree[v].size()-bb)*(tree[v].size()-bb-1);
    if(bb+aa != nn){
        ans -= 1ll*(tree[v].size()-1)*(n-bb-aa+1)*(n-bb-aa);
    }
    // if(v == 10){
    //     cout << bb+aa << endl;
    // }
    return bb+aa;
}

int main(){
    // freopen("a.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i<m; i++){
        int a, b; cin >> a >> b;
        --a; --b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    curComp = n-1;
    for(int i = 0; i<n; i++) if(!visited[i]) {
        nn = 0;
        tarjan(i, -1);
        ans += 1ll*nn*(nn-1)*(nn-2);
        gen(i, 0);
        getSiz(i, -1);
    }
    // for(int i = 0; i<n; i++) if(isCut[i]) cout << i+1 << endl;
    // for(int i = 0; i<MAXN; i++){
    //     if(tree[i].size()){
    //         cout << i+1 << endl;
    //         for(auto j : tree[i]) cout << j+1 << " ";
    //         cout << endl << endl;;
    //     }
    // }
    cout << ans << endl;
}

Subtask #1
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	14444 KB	Output is correct
2	Correct	10 ms	14464 KB	Output is correct
3	Correct	10 ms	14444 KB	Output is correct
4	Correct	10 ms	14444 KB	Output is correct
5	Correct	10 ms	14444 KB	Output is correct
6	Correct	10 ms	14444 KB	Output is correct
7	Correct	10 ms	14444 KB	Output is correct
8	Correct	10 ms	14444 KB	Output is correct
9	Correct	10 ms	14444 KB	Output is correct
10	Correct	10 ms	14444 KB	Output is correct
11	Correct	11 ms	14444 KB	Output is correct
12	Incorrect	10 ms	14444 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	14444 KB	Output is correct
2	Correct	10 ms	14464 KB	Output is correct
3	Correct	10 ms	14444 KB	Output is correct
4	Correct	10 ms	14444 KB	Output is correct
5	Correct	10 ms	14444 KB	Output is correct
6	Correct	10 ms	14444 KB	Output is correct
7	Correct	10 ms	14444 KB	Output is correct
8	Correct	10 ms	14444 KB	Output is correct
9	Correct	10 ms	14444 KB	Output is correct
10	Correct	10 ms	14444 KB	Output is correct
11	Correct	11 ms	14444 KB	Output is correct
12	Incorrect	10 ms	14444 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #3
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	131 ms	36044 KB	Output is correct
2	Correct	125 ms	36060 KB	Output is correct
3	Incorrect	141 ms	32992 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #4
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	14572 KB	Output is correct
2	Correct	10 ms	14572 KB	Output is correct
3	Correct	10 ms	14572 KB	Output is correct
4	Correct	11 ms	14700 KB	Output is correct
5	Correct	11 ms	14700 KB	Output is correct
6	Correct	11 ms	14572 KB	Output is correct
7	Correct	11 ms	14720 KB	Output is correct
8	Correct	10 ms	14572 KB	Output is correct
9	Correct	11 ms	14572 KB	Output is correct
10	Incorrect	11 ms	14572 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #5
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	133 ms	26724 KB	Output is correct
2	Correct	160 ms	28024 KB	Output is correct
3	Correct	131 ms	27948 KB	Output is correct
4	Correct	136 ms	27896 KB	Output is correct
5	Correct	132 ms	28072 KB	Output is correct
6	Correct	162 ms	37732 KB	Output is correct
7	Correct	168 ms	34148 KB	Output is correct
8	Correct	158 ms	32484 KB	Output is correct
9	Correct	159 ms	31076 KB	Output is correct
10	Incorrect	139 ms	27936 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	130 ms	26856 KB	Output is correct
2	Correct	129 ms	28132 KB	Output is correct
3	Incorrect	138 ms	28008 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	14444 KB	Output is correct
2	Correct	10 ms	14464 KB	Output is correct
3	Correct	10 ms	14444 KB	Output is correct
4	Correct	10 ms	14444 KB	Output is correct
5	Correct	10 ms	14444 KB	Output is correct
6	Correct	10 ms	14444 KB	Output is correct
7	Correct	10 ms	14444 KB	Output is correct
8	Correct	10 ms	14444 KB	Output is correct
9	Correct	10 ms	14444 KB	Output is correct
10	Correct	10 ms	14444 KB	Output is correct
11	Correct	11 ms	14444 KB	Output is correct
12	Incorrect	10 ms	14444 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	14444 KB	Output is correct
2	Correct	10 ms	14464 KB	Output is correct
3	Correct	10 ms	14444 KB	Output is correct
4	Correct	10 ms	14444 KB	Output is correct
5	Correct	10 ms	14444 KB	Output is correct
6	Correct	10 ms	14444 KB	Output is correct
7	Correct	10 ms	14444 KB	Output is correct
8	Correct	10 ms	14444 KB	Output is correct
9	Correct	10 ms	14444 KB	Output is correct
10	Correct	10 ms	14444 KB	Output is correct
11	Correct	11 ms	14444 KB	Output is correct
12	Incorrect	10 ms	14444 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

답안 #321285

Compilation message