oj.uz

답안 #901623

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
901623 2024-01-09T17:37:24 Z SalihSahin 철인 이종 경기 (APIO18_duathlon) C++17
0 / 100
 101 ms 43860 KB 
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
using namespace std;
 
const int mod = 1e9 + 7;
const int inf = 1e17*2;
const int N = 2e5 + 5;

vector<int> adj[N], low(N), in(N), vis(N), par(N), sz(N), sub(N);
int timer = 0;
vector<pair<int, int> > bridge;

void dfs(int node, int par){
    vis[node] = 1;
    in[node] = low[node] = timer++;

    for(auto itr: adj[node]){
        if(itr == par) continue;
        if(vis[itr]){
            low[node] = min(low[node], in[itr]);
        }
        else{
            dfs(itr, node);
            low[node] = min(low[node], low[itr]);
            if(in[node] < low[itr]){
                bridge.pb(mp(min(node, itr), max(node, itr)));
            }
        }
    }
}

int find(int a){
    if(a == par[a]) return a;
    return par[a] = find(par[a]);
}

void merge(int a, int b){
    par[find(b)] = find(a);
}

vector<int> adj2[N];

void dfs2(int node, int &cnt){
    cnt++;
    vis[node] = 1;

    for(auto itr: adj2[node]){
        if(!vis[itr]){
            dfs2(itr, cnt);
            merge(node, itr);
        }
    }
}

vector<int> adjb[N];

void subcalc(int node, int par){
    for(auto itr: adjb[node]){
        if(itr != par){
            subcalc(itr, node);
            sub[node] += sub[itr];
        }
    }
    sub[node] += sz[node];
}

void dfs3(int node, int par, int total, int &ans){
    vector<int> v;
    for(auto itr: adjb[node]){
        if(itr != par) v.pb(sub[itr]); 
    }
    if(node != par) v.pb(total - sub[node]);

    for(auto itr: v){
        ans += sz[node] * itr * (total - sz[node] - itr);
    }

    for(auto itr: adjb[node]){
        if(itr != par){
            dfs3(itr, node, total, ans);
        }
    }
}

int32_t main(){
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int n, m;
    cin>>n>>m;

    vector<pair<int, int> > edge(m);
    for(int i = 0; i < m; i++){
        int u, v;
        cin>>u>>v;
        if(u > v) swap(u, v);
        edge[i] = mp(u, v);
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for(int i = 1; i <= n; i++){
        dfs(i, i);
    }
    sort(bridge.begin(), bridge.end());
    sort(edge.begin(), edge.end());
    int bind = 0;

    for(int i = 0; i < m; i++){
        if(bind < bridge.size() && bridge[bind] == edge[i]){
            bind++;
            continue;
        }
        auto[u, v] = edge[i];
        adj2[u].pb(v);
        adj2[v].pb(u);
    }
    for(int i = 1; i <= n; i++){
        vis[i] = 0;
        par[i] = i;
        sz[i] = 1;
    }
    int cnt = 0, ans = 0;

    for(int i = 1; i <= n; i++){
        if(!vis[i]){
            dfs2(i, cnt);
            sz[i] = cnt;
            ans += cnt * (cnt - 1) * (cnt - 2); // 3 here, 0 other
            ans += (cnt - 1) * (cnt - 1) * (n - cnt) * 2; // 2 here, 1 other
            cnt = 0;
        }
    }

    for(int i = 0; i < bridge.size(); i++){
        auto[u, v] = bridge[i];
        u = find(u), v = find(v);
        adjb[u].pb(v);
        adjb[v].pb(u);
    }
    for(int i = 1; i <= n; i++){
        vis[i] = 0;
    }

    subcalc(find(1), find(1));
    dfs3(find(1), find(1), n, ans);
    cout<<ans<<endl;
    return 0;
}

Compilation message

count_triplets.cpp: In function 'int32_t main()':
count_triplets.cpp:110:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         if(bind < bridge.size() && bridge[bind] == edge[i]){
      |            ~~~~~^~~~~~~~~~~~~~~
count_triplets.cpp:135:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for(int i = 0; i < bridge.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 23900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 23900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 35784 KB Output is correct
2 Correct 88 ms 35780 KB Output is correct
3 Correct 89 ms 35660 KB Output is correct
4 Correct 85 ms 35824 KB Output is correct
5 Correct 87 ms 35652 KB Output is correct
6 Correct 101 ms 42944 KB Output is correct
7 Correct 86 ms 41156 KB Output is correct
8 Correct 88 ms 39616 KB Output is correct
9 Correct 81 ms 38336 KB Output is correct
10 Incorrect 74 ms 35776 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 23900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 23900 KB Output isn't correct
2 Halted 0 ms 0 KB -