답안 #217644

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
217644 2020-03-30T11:34:17 Z VEGAnn 철인 이종 경기 (APIO18_duathlon) C++14
31 / 100
1000 ms 20576 KB
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define PB push_back
#define pii pair<int,int>
#define ft first
#define sd second
#define MP make_pair
using namespace std;
typedef long long ll;
const int N = 100100;
const int M = 200100;
const int oo = 2e9;
vector<int> g[N];
vector<pii> gr[N];
int n, m, tin[N], fup[N], tt = 0, U[M], V[M], pr[N], siz[N];
int nw_siz[N];
bool mrk[N], bridge[M];
ll ans = 0, SZ;

void dfs(int v, int p){
    mrk[v] = 1;
    tin[v] = fup[v] = ++tt;

    for (int nm : g[v]){
        int u = (U[nm] == v ? V[nm] : U[nm]);

        if (u == p) continue;

        if (mrk[u])
            fup[v] = min(fup[v], tin[u]);
        else {
            dfs(u, v);
            fup[v] = min(fup[v], fup[u]);

            if (fup[u] > tin[v])
                bridge[nm] = 1;
        }
    }
}

int get(int x) { return (x == pr[x] ? x : pr[x] = get(pr[x])); }

void dfs1(int v, int p){
    nw_siz[v] = siz[v];
    mrk[v] = 1;

    for (pii u : gr[v]){
        if (u.sd == p) continue;

        dfs1(u.sd, v);
        nw_siz[v] += nw_siz[u.sd];
    }
}

void dfs2(int v, int p){
    ans += ll(siz[v]) * (ll(siz[v]) - 1ll) * (ll(siz[v]) - 2ll) / 2ll; // first

    ans += (SZ - ll(siz[v])) * (ll(siz[v]) - 1ll) * (ll(siz[v]) - 1ll);

    ll sum = 0ll;

    for (int it = 0; it < sz(gr[v]); ){

        int j = it;
        ll sim = 0;

        while (j < sz(g[v]) && gr[v][it].ft == gr[v][j].ft){
            int u = gr[v][j].sd;
            if (u != p) {
                dfs2(u, v);
                ans += sim * ll(nw_siz[u]);
                sim += ll(nw_siz[u]);
            } else {
                ans += sim * (SZ - ll(nw_siz[v]));
                sim += (SZ - ll(nw_siz[v]));
            }
            j++;
        }

        ans += sum * ll(siz[v]) * sim;

        sum += sim;

        it = j;
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

//    freopen("in.txt","r",stdin);

    cin >> n >> m;

    for (int i = 0; i < m; i++){
        cin >> U[i] >> V[i];
        U[i]--; V[i]--;

        g[U[i]].PB(i);
        g[V[i]].PB(i);
    }

    for (int i = 0; i < n; i++) {
        if (!mrk[i])
            dfs(i, -1);

        pr[i] = i;
        siz[i] = 1;
    }


    for (int i = 0; i < m; i++) {
        if (bridge[i]) continue;

        int x = get(U[i]), y = get(V[i]);

        if (x == y) continue;

        pr[x] = y;
        siz[y] += siz[x];
    }

    for (int i = 0; i < m; i++)
        if (bridge[i]){
            int x = get(U[i]), y = get(V[i]);

            gr[x].PB(MP(U[i], y));
            gr[y].PB(MP(V[i], x));
        }

    fill(mrk, mrk + n, 0);
    for (int i = 0; i < n; i++)
        if (sz(g[i])){
            sort(all(gr[i]));
        }

    for (int i = 0; i < n; i++){
        if (get(i) != i) continue;
        if (mrk[i]) continue;

        dfs1(i, -1);
        SZ = nw_siz[i];
        dfs2(i, -1);
    }

    cout << ans * 2;

    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 8 ms 5120 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 10 ms 5120 KB Output is correct
5 Correct 10 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Execution timed out 1085 ms 5120 KB Time limit exceeded
8 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 8 ms 5120 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 10 ms 5120 KB Output is correct
5 Correct 10 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Execution timed out 1085 ms 5120 KB Time limit exceeded
8 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 19732 KB Output is correct
2 Correct 112 ms 19704 KB Output is correct
3 Correct 159 ms 17912 KB Output is correct
4 Correct 147 ms 19064 KB Output is correct
5 Correct 191 ms 16012 KB Output is correct
6 Correct 189 ms 17272 KB Output is correct
7 Correct 178 ms 16096 KB Output is correct
8 Correct 178 ms 16568 KB Output is correct
9 Correct 163 ms 15232 KB Output is correct
10 Correct 160 ms 15456 KB Output is correct
11 Correct 123 ms 13772 KB Output is correct
12 Correct 114 ms 13536 KB Output is correct
13 Correct 107 ms 13560 KB Output is correct
14 Correct 117 ms 13244 KB Output is correct
15 Correct 83 ms 12792 KB Output is correct
16 Correct 78 ms 12536 KB Output is correct
17 Correct 11 ms 7168 KB Output is correct
18 Correct 11 ms 7168 KB Output is correct
19 Correct 11 ms 7168 KB Output is correct
20 Correct 10 ms 7168 KB Output is correct
21 Correct 10 ms 7168 KB Output is correct
22 Correct 11 ms 7168 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5248 KB Output is correct
2 Correct 8 ms 5248 KB Output is correct
3 Correct 8 ms 5248 KB Output is correct
4 Correct 8 ms 5248 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 8 ms 5220 KB Output is correct
7 Correct 8 ms 5248 KB Output is correct
8 Correct 9 ms 5248 KB Output is correct
9 Correct 9 ms 5296 KB Output is correct
10 Correct 9 ms 5248 KB Output is correct
11 Correct 8 ms 5248 KB Output is correct
12 Correct 9 ms 5248 KB Output is correct
13 Correct 8 ms 5248 KB Output is correct
14 Correct 10 ms 5168 KB Output is correct
15 Correct 8 ms 5120 KB Output is correct
16 Correct 8 ms 5248 KB Output is correct
17 Correct 9 ms 5248 KB Output is correct
18 Correct 10 ms 5248 KB Output is correct
19 Correct 8 ms 5248 KB Output is correct
20 Correct 8 ms 5248 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 16276 KB Output is correct
2 Correct 186 ms 16248 KB Output is correct
3 Correct 156 ms 16248 KB Output is correct
4 Correct 196 ms 16352 KB Output is correct
5 Correct 152 ms 16248 KB Output is correct
6 Correct 210 ms 20576 KB Output is correct
7 Correct 198 ms 19520 KB Output is correct
8 Correct 190 ms 18552 KB Output is correct
9 Correct 272 ms 17656 KB Output is correct
10 Correct 163 ms 16376 KB Output is correct
11 Correct 159 ms 16248 KB Output is correct
12 Correct 154 ms 16248 KB Output is correct
13 Correct 181 ms 16248 KB Output is correct
14 Correct 126 ms 15736 KB Output is correct
15 Correct 118 ms 15100 KB Output is correct
16 Correct 74 ms 12920 KB Output is correct
17 Correct 96 ms 16748 KB Output is correct
18 Correct 93 ms 16756 KB Output is correct
19 Correct 87 ms 16604 KB Output is correct
20 Correct 95 ms 16744 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5248 KB Output is correct
2 Correct 8 ms 5120 KB Output is correct
3 Execution timed out 1089 ms 5120 KB Time limit exceeded
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 148 ms 16248 KB Output is correct
2 Correct 163 ms 16104 KB Output is correct
3 Execution timed out 1090 ms 15224 KB Time limit exceeded
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 8 ms 5120 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 10 ms 5120 KB Output is correct
5 Correct 10 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Execution timed out 1085 ms 5120 KB Time limit exceeded
8 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 8 ms 5120 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 10 ms 5120 KB Output is correct
5 Correct 10 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Execution timed out 1085 ms 5120 KB Time limit exceeded
8 Halted 0 ms 0 KB -