oj.uz

답안 #974327

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
974327 2024-05-03T08:32:02 Z efedmrlr 철인 이종 경기 (APIO18_duathlon) C++17
23 / 100
 1000 ms 1048576 KB 
#include <bits/stdc++.h>

#define int long long int
#define lli int
#define ld long double
#define pb push_back
#define MP make_pair
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 2e5 + 5;
const int INF = 1e9 + 500;
int n, m;
vector<vector<array<int, 2> > > adj(N, vector<array<int, 2> >());
int tim = 0;
vector<int> tin(N, -1), low(N, 0);
vector<array<int, 2> > edg(N);
vector<bool> isBr(N, 0);
vector<int> comp(N, -1), cmpsz(N, 0);
vector<vector<int> > cadj(N, vector<int>());
vector<int> subsz(N, 0);
vector<int> rt;
lli ans = 0;
void find_bridge(int node, int par) {
    tin[node] = low[node] = tim++;
    for(auto c : adj[node]) {
        if(c[0] == par) {
            continue;
        }
        if(tin[c[0]] != -1) {
            low[node] = min(low[node], tin[c[0]]);
        }
        else {
            find_bridge(c[0], node);
            low[node] = min(low[node], low[c[0]]);
            // cout << "c[1]:"  << c[1] << " node:" << node << " lowc0:" << low[c[0]] << " tin[node]:" << tin[node] << "\n";
            if(low[c[0]] > tin[node]) {
                //bridge
                isBr[c[1]] = 1;
            }
        }
    }
}

void get_comp(int node, int par, int cm) {
    comp[node] = cm;
    cmpsz[cm]++;
    for(auto c : adj[node]) {
        if(c[0] == par || isBr[c[1]]) continue;
        get_comp(c[0], node, cm);
    }
}

void prec(int node, int par) {
    subsz[node] = cmpsz[node];
    for(auto c : cadj[node]) {
        if(c == par) continue;
        prec(c, node);
        subsz[node] += subsz[c];
    }
}

void dfs(int node, int par, int root) {
    lli ret = 0;
    lli x = subsz[root] - cmpsz[node];
    for(auto c : cadj[node]) {
        if(c == par) {
            int sbt = subsz[root] - subsz[node];
            ret += 1ll * cmpsz[node] * sbt * (x - sbt); 
            continue;
        }
        int sbt = subsz[c];
        ret += 1ll * cmpsz[node] * sbt * (x - sbt);
        dfs(c, node, root);
    }
    ans += ret;
}


void solve() {
    cin >> n >> m;
    REP(i, m) {
        int u, v;
        cin >> u >> v;
        edg[i] = {u, v};
        adj[u].pb({v, i});
        adj[v].pb({u, i});
    }    
    for(int i = 1; i <= n; i++) {
        if(tin[i] != -1) continue;
        rt.pb(i);
        find_bridge(i, 0);
    }
    int cur = 1;
    for(int i = 1; i <= n; i++) {
        if(comp[i] == -1) {
            get_comp(i, 0, cur++);
        }
        // cout << "i:" << i << " comp:" << comp[i] << "\n";
    }
    // assert(cur == n + 1);
    for(int i = 0; i < m; i++) {
        if(isBr[i]) {
            // cout << edg[i][0] << " " << edg[i][1] << "\n";
            cadj[comp[edg[i][0]]].pb(edg[i][1]);
            cadj[comp[edg[i][1]]].pb(edg[i][0]);
        }
    }
    for(auto c : rt) {
        prec(comp[c], 0);
    }
    // for(int i = 1; i < cur; i++) {
    //     ans += 1ll * cmpsz[i] * (cmpsz[i] - 1) * (cmpsz[i] - 2);
    // }
    for(int c : rt) {
        
        dfs(comp[c], 0, comp[c]);
    }
    cout << ans << "\n";
}


signed main() {
    fastio();
    solve();
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 597 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 597 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1063 ms 757940 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 29644 KB Output is correct
2 Correct 64 ms 29724 KB Output is correct
3 Correct 61 ms 29532 KB Output is correct
4 Correct 62 ms 29540 KB Output is correct
5 Correct 65 ms 29520 KB Output is correct
6 Correct 89 ms 33788 KB Output is correct
7 Correct 71 ms 32848 KB Output is correct
8 Correct 85 ms 32080 KB Output is correct
9 Correct 68 ms 31060 KB Output is correct
10 Correct 67 ms 29704 KB Output is correct
11 Correct 71 ms 31056 KB Output is correct
12 Correct 63 ms 30820 KB Output is correct
13 Correct 62 ms 30768 KB Output is correct
14 Correct 57 ms 30036 KB Output is correct
15 Correct 53 ms 29400 KB Output is correct
16 Correct 37 ms 26836 KB Output is correct
17 Correct 47 ms 30812 KB Output is correct
18 Correct 48 ms 30520 KB Output is correct
19 Correct 52 ms 31316 KB Output is correct
20 Correct 46 ms 30764 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 20824 KB Output is correct
2 Correct 8 ms 20904 KB Output is correct
3 Runtime error 587 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 29604 KB Output is correct
2 Correct 64 ms 29524 KB Output is correct
3 Runtime error 610 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 597 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 597 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -