oj.uz

Submission #402721

# Submission time Handle Problem Language Result Execution time Memory
402721 2021-05-12T09:47:22 Z dxz05 Duathlon (APIO18_duathlon) C++14
8 / 100
 845 ms 1048580 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << "[" << H << "]";
    debug_out(T...);
}

#ifdef dddxxz
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SZ(s) ((int)s.size())
#define all(x) (x).begin(), (x).end()
#define revall(x) (x).rbegin(), (x).rend()

clock_t startTime;

double getCurrentTime() {
    return (double) (clock() - startTime) / CLOCKS_PER_SEC;
}

typedef long long ll;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const double eps = 0.00001;
const int MOD = 1e9 + 7;
const int INF = 1000000101;
const long long LLINF = 1223372000000000555;
const int N = 1e6 + 3e2;
const int M = 2222;

int n, m;
vector<int> g[N];

int cnt = 0, color[N];
bool cycle = false;
void dfs(int v, int p){
    color[v] = 1;
    cnt++;
    for (int u : g[v]){
        if (u == p) continue;
        if (color[u] == 1) cycle = true;
        if (color[u] == 0) dfs(u, v);
    }
    color[v] = 2;
}

void Subtask_3(){
    ll ans = 0;
    for (int i = 1; i <= n; i++){
        if (color[i] == 0){
            cnt = 0;
            cycle = false;
            dfs(i, 0);
            ans += 1ll * cnt * (cnt - 1) * (cnt - 2) / (cycle ? 1 : 3);
        }
    }

    cout << ans;

    exit(0);
}

ll ans5 = 0;
int subtree[N];
bool used[N];
void dfs2(int v, int p){
    used[v] = true;
    subtree[v] = 1;
    for (int u : g[v]){
        if (u != p){
            dfs2(u, v);
            subtree[v] += subtree[u];
        }
    }

    for (int u : g[v]){
        if (u != p){
            ll x = subtree[u], y = n - subtree[u] - 1;
            ans5 += x * y;
        } else {
            ll x = subtree[v] - 1, y = n - x - 1;
            ans5 += x * y;
        }
    }

}

void Subtask_5(){
    for (int i = 1; i <= n; i++){
        if (!used[i]) dfs2(i, i);
    }
    cout << ans5 << endl;
    exit(0);
}

void solve(int TC) {
    cin >> n >> m;

    bool ok3 = true;
    while (m--) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);

        ok3 &= g[u].size() <= 2;
        ok3 &= g[v].size() <= 2;
    }

    if (ok3){
        Subtask_3();
    }

    Subtask_5();

}


int main() {
    startTime = clock();
    cin.tie(nullptr); cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    bool llololcal = false;
#ifdef dddxxz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    llololcal = true;
#endif

    int TC = 1;
    //  cin >> TC;

    for (int test = 1; test <= TC; test++) {
        //debug(test);
        //cout << "Case #" << test << ": ";
        solve(test);
    }

    if (llololcal) cerr << endl << "Time: " << int(getCurrentTime() * 1000) << " ms" << endl;

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 533 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 533 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 30764 KB Output is correct
2 Correct 76 ms 30692 KB Output is correct
3 Correct 60 ms 29100 KB Output is correct
4 Correct 71 ms 29800 KB Output is correct
5 Correct 61 ms 28528 KB Output is correct
6 Correct 70 ms 28552 KB Output is correct
7 Correct 65 ms 28100 KB Output is correct
8 Correct 62 ms 28356 KB Output is correct
9 Correct 60 ms 27712 KB Output is correct
10 Correct 60 ms 28048 KB Output is correct
11 Correct 51 ms 27332 KB Output is correct
12 Correct 55 ms 27296 KB Output is correct
13 Correct 50 ms 27224 KB Output is correct
14 Correct 48 ms 27156 KB Output is correct
15 Correct 40 ms 26840 KB Output is correct
16 Correct 40 ms 26776 KB Output is correct
17 Correct 15 ms 24140 KB Output is correct
18 Correct 18 ms 24140 KB Output is correct
19 Correct 18 ms 24140 KB Output is correct
20 Correct 15 ms 24212 KB Output is correct
21 Correct 15 ms 24140 KB Output is correct
22 Correct 15 ms 24192 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23776 KB Output is correct
2 Correct 16 ms 23800 KB Output is correct
3 Correct 15 ms 23756 KB Output is correct
4 Correct 15 ms 23884 KB Output is correct
5 Correct 17 ms 23816 KB Output is correct
6 Correct 15 ms 23884 KB Output is correct
7 Correct 15 ms 23872 KB Output is correct
8 Correct 14 ms 23884 KB Output is correct
9 Correct 16 ms 23884 KB Output is correct
10 Incorrect 15 ms 23816 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 27780 KB Output is correct
2 Correct 59 ms 27716 KB Output is correct
3 Correct 61 ms 27800 KB Output is correct
4 Correct 67 ms 27784 KB Output is correct
5 Correct 62 ms 27780 KB Output is correct
6 Correct 66 ms 29280 KB Output is correct
7 Correct 67 ms 30524 KB Output is correct
8 Correct 65 ms 29780 KB Output is correct
9 Correct 72 ms 29008 KB Output is correct
10 Incorrect 65 ms 27840 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23820 KB Output is correct
2 Correct 15 ms 23836 KB Output is correct
3 Runtime error 694 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 27436 KB Output is correct
2 Correct 68 ms 27428 KB Output is correct
3 Runtime error 845 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 533 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 533 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -