oj.uz

답안 #397287

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
397287 2021-05-01T20:04:53 Z osaaateiasavtnl 철인 이종 경기 (APIO18_duathlon) C++14
23 / 100
 180 ms 65340 KB 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <fstream>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define x first
#define y second
#define Time (double)clock()/CLOCKS_PER_SEC
#define debug(x) std::cerr << #x << ": " << x << '\n';
#define FOR(i, n) for (int i = 0; i < n; ++i)
#define FORN(i, n) for (int i = 1; i <= n; ++i)
#define pb push_back
#define trav(a, x) for (auto& a : x)
using vi = vector<int>;
template <typename T>
std::istream& operator >>(std::istream& input, std::vector<T>& data)
{
    for (T& x : data)
        input >> x;
    return input;
}
template <typename T>
std::ostream& operator <<(std::ostream& output, const pair <T, T> & data)
{
    output << "(" << data.x << "," << data.y << ")";
    return output;
}
template <typename T>
std::ostream& operator <<(std::ostream& output, const std::vector<T>& data)
{
    for (const T& x : data)
        output << x << " ";
    return output;
}
ll div_up(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll div_down(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down 
ll math_mod(ll a, ll b) { return a - b * div_down(a, b); }
#define tcT template<class T
#define tcTU tcT, class U
tcT> using V = vector<T>; 
tcT> void re(V<T>& x) { 
    trav(a, x)
        cin >> a;
}
tcT> bool ckmin(T& a, const T& b) {
    return b < a ? a = b, 1 : 0; 
} // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0; 
}
ll gcd(ll a, ll b) {
    while (b) {
        tie(a, b) = mp(b, a % b);
    }
    return a;
}
const int N = 5e5+7;
int n, m;
vi g[N], tree[N];
int num[N], up[N];
int ptr = 1;
bool cut[N];
void dfs1(int u) {
    up[u] = num[u] = ptr++;
    trav (v, g[u]) {
        if (num[v]) {
            ckmin(up[u], num[v]);
        }
        else {
            tree[u].app(v);
            dfs1(v);
            if (up[v] >= num[u]) {
                cut[v] = 1;
            }
        }
    }
}
int cla;
vi T[N];
void dfs2(int u, int cur) {
    if (cur) {
        T[u].app(cur);
        T[cur].app(u);
    }
    trav (v, tree[u]) {
        if (cut[v]) {
            cla++;
            T[u].app(cla);
            T[cla].app(u);
            dfs2(v, cla);
        }
        else {
            dfs2(v, cur);
        }
    }
}
bool used[N];
int sub[N];
void dfs3(int u, int p) {
    used[u] = 1;
    sub[u] = u <= n;
    trav (v, T[u]) {
        if (v != p) {
            dfs3(v, u);
            sub[u] += sub[v];
        }
    }
}
int ans = 0;
void dfs4(int u, int p, int tot) {
    trav (v, T[u]) {
        if (v != p) {
            dfs4(v, u, tot);
            if (u <= n) {
                int comp = T[v].size();
                ans -= (comp - 1) * (tot - sub[v]) * (tot - sub[v] - 1);
            }
            else {
                int comp = T[u].size();
                ans -= (comp - 1) * sub[v] * (sub[v] - 1);
            }
        }
    }    
}
signed main() {
    #ifdef LOCAL
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> m;
    FOR (i, m) {
        int u, v;
        cin >> u >> v;
        g[u].app(v); g[v].app(u);
    }
    cla = n;
    FORN (u, n) {
        if (!num[u]) {
            dfs1(u);
            dfs2(u, 0);
        }
    }
    FORN (u, n + m) {
        //debug(u);
        //debug(T[u]);
        sort(all(T[u]));
        T[u].resize(unique(all(T[u])) - T[u].begin());
    }
    FORN (u, n) {
        if (!used[u]) {
            dfs3(u, u);
            ans += sub[u] * (sub[u] - 1) * (sub[u] - 2);
            dfs4(u, u, sub[u]);
        }
    }
    cout << ans << endl;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 35584 KB Output is correct
2 Correct 19 ms 35488 KB Output is correct
3 Correct 21 ms 35524 KB Output is correct
4 Correct 19 ms 35532 KB Output is correct
5 Correct 19 ms 35508 KB Output is correct
6 Correct 19 ms 35532 KB Output is correct
7 Correct 19 ms 35532 KB Output is correct
8 Incorrect 19 ms 35532 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 35584 KB Output is correct
2 Correct 19 ms 35488 KB Output is correct
3 Correct 21 ms 35524 KB Output is correct
4 Correct 19 ms 35532 KB Output is correct
5 Correct 19 ms 35508 KB Output is correct
6 Correct 19 ms 35532 KB Output is correct
7 Correct 19 ms 35532 KB Output is correct
8 Incorrect 19 ms 35532 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 35688 KB Output is correct
2 Correct 20 ms 35688 KB Output is correct
3 Correct 20 ms 35672 KB Output is correct
4 Correct 20 ms 35788 KB Output is correct
5 Correct 20 ms 35788 KB Output is correct
6 Correct 22 ms 35684 KB Output is correct
7 Correct 19 ms 35788 KB Output is correct
8 Correct 20 ms 35788 KB Output is correct
9 Correct 20 ms 35660 KB Output is correct
10 Correct 21 ms 35816 KB Output is correct
11 Correct 21 ms 35660 KB Output is correct
12 Correct 21 ms 35676 KB Output is correct
13 Correct 21 ms 35660 KB Output is correct
14 Correct 20 ms 35660 KB Output is correct
15 Correct 20 ms 35684 KB Output is correct
16 Correct 20 ms 35628 KB Output is correct
17 Correct 20 ms 35688 KB Output is correct
18 Correct 20 ms 35704 KB Output is correct
19 Correct 20 ms 35660 KB Output is correct
20 Correct 20 ms 35688 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 52744 KB Output is correct
2 Correct 131 ms 52676 KB Output is correct
3 Correct 164 ms 52820 KB Output is correct
4 Correct 136 ms 52688 KB Output is correct
5 Correct 138 ms 52620 KB Output is correct
6 Correct 180 ms 59588 KB Output is correct
7 Correct 158 ms 57312 KB Output is correct
8 Correct 158 ms 56184 KB Output is correct
9 Correct 147 ms 54852 KB Output is correct
10 Correct 166 ms 52628 KB Output is correct
11 Correct 133 ms 52676 KB Output is correct
12 Correct 143 ms 52624 KB Output is correct
13 Correct 155 ms 52624 KB Output is correct
14 Correct 169 ms 51696 KB Output is correct
15 Correct 124 ms 50756 KB Output is correct
16 Correct 83 ms 46816 KB Output is correct
17 Correct 95 ms 51968 KB Output is correct
18 Correct 100 ms 52016 KB Output is correct
19 Correct 96 ms 52244 KB Output is correct
20 Correct 112 ms 52024 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 35664 KB Output is correct
2 Correct 21 ms 35708 KB Output is correct
3 Correct 20 ms 35684 KB Output is correct
4 Incorrect 20 ms 35660 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 52728 KB Output is correct
2 Correct 161 ms 52720 KB Output is correct
3 Correct 144 ms 52708 KB Output is correct
4 Incorrect 144 ms 52868 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 35584 KB Output is correct
2 Correct 19 ms 35488 KB Output is correct
3 Correct 21 ms 35524 KB Output is correct
4 Correct 19 ms 35532 KB Output is correct
5 Correct 19 ms 35508 KB Output is correct
6 Correct 19 ms 35532 KB Output is correct
7 Correct 19 ms 35532 KB Output is correct
8 Incorrect 19 ms 35532 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 35584 KB Output is correct
2 Correct 19 ms 35488 KB Output is correct
3 Correct 21 ms 35524 KB Output is correct
4 Correct 19 ms 35532 KB Output is correct
5 Correct 19 ms 35508 KB Output is correct
6 Correct 19 ms 35532 KB Output is correct
7 Correct 19 ms 35532 KB Output is correct
8 Incorrect 19 ms 35532 KB Output isn't correct
9 Halted 0 ms 0 KB -