oj.uz

답안 #901634

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
901634 2024-01-09T18:50:07 Z SalihSahin 철인 이종 경기 (APIO18_duathlon) C++17
0 / 100
 84 ms 48048 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), cl(N), clsz(N);
int timer = 0;
vector<pair<int, int> > bridge;

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

    for(auto itr: adj[node]){
        if(itr == par) continue;
        if(vis[itr]){
            low[node] = min(low[node], in[itr]);
        }
        else{
            dfs(itr, node, cal, cnt);
            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){
    vis[node] = 1;

    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){
    vis[node] = 1;

    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);
        }
    }
}

void dfs4(int node, int par, int &val){
    val += sz[node];
    for(auto itr: adjb[node]){
        if(itr == par) continue;
        dfs4(itr, node, val);
    }
}

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);
    }

    int calss = 0;
    for(int i = 1; i <= n; i++){
        if(vis[i]) continue;
        calss++;
        int cnto = 0;
        dfs(i, i, calss, cnto);
        clsz[calss] = cnto;

    }
    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) * (clsz[cl[i]] - cnt) * 2; // 2 here, 1 other
            cnt = 0;
        }
    }
    cout<<ans<<endl;

    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;
    }
    for(int i = 1; i <= n; i++){
        if(vis[find(i)]) continue; 
        subcalc(find(i), find(i));
    }
    for(int i = 1; i <= n; i++){
        vis[i] = 0;
    }

    for(int i = 1; i <= n; i++){
        if(vis[find(i)]) continue;
        int k = find(i);
        int val = 0;
        dfs4(k, k, val);
        //cout<<i<<" -> "<<k<<" "<<val<<endl;
        dfs3(k, k, val, ans);
    }
    cout<<ans<<endl;
    return 0;
}

Compilation message

count_triplets.cpp: In function 'int32_t main()':
count_triplets.cpp:131: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]
  131 |         if(bind < bridge.size() && bridge[bind] == edge[i]){
      |            ~~~~~^~~~~~~~~~~~~~~
count_triplets.cpp:157: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]
  157 |     for(int i = 0; i < bridge.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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