oj.uz

Submission #402792

# Submission time Handle Problem Language Result Execution time Memory
402792 2021-05-12T11:10:36 Z dxz05 Duathlon (APIO18_duathlon) C++14
31 / 100
 934 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];

set<pair<int, int>> deleted;

bool check(int s, int c, int f){
    queue<int> q;
    vector<int> parent(n + 1);
    vector<bool> used(n + 1);
    q.push(c);
    while (!q.empty()){
        int x = q.front(); q.pop();
        for (int y : g[x]){
            if (!used[y] && y != f){
                used[y] = true;
                parent[y] = x;
                q.push(y);
            }
        }
    }

    if (!used[s]) return false;

    int ss = s;
    while (ss != c){
        deleted.insert(make_pair(ss, parent[ss]));
        deleted.insert(make_pair(parent[ss], ss));
        ss = parent[ss];
    }

    used.assign(n + 1, 0);

    q.push(c);
    while (!q.empty()){
        int x = q.front(); q.pop();
        for (int y : g[x]){
            if (!used[y] && deleted.find(make_pair(x, y)) == deleted.end() && y != s){
                used[y] = true;
                q.push(y);
            }
        }
    }

    deleted.clear();

    if (!used[f]) return false;
//    cout << s << ' ' << c << ' ' << f << endl;
    return true;
}

void Subtask_1(){
    int ans = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            for (int k = 1; k <= n; k++){
                if (i != j && i != k && j != k) ans += check(i, j, k);
            }
        }
    }
    cout << ans;
    exit(0);
}

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 = cnt - subtree[u] - 1;
            ans5 += x * y;
        } else {
            ll x = subtree[v] - 1, y = cnt - x - 1;
            ans5 += x * y;
        }
    }

}

void Subtask_5(){
    memset(color, 0, sizeof(color));
    for (int i = 1; i <= n; i++){
        if (!used[i]){
            cnt = 0;
            dfs(i, 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 (n <= 50 && m <= 100) {
        Subtask_1();
    }

    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 Correct 14 ms 23704 KB Output is correct
2 Correct 14 ms 23780 KB Output is correct
3 Correct 14 ms 23756 KB Output is correct
4 Correct 14 ms 23812 KB Output is correct
5 Correct 17 ms 23756 KB Output is correct
6 Correct 15 ms 23812 KB Output is correct
7 Incorrect 14 ms 23816 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23704 KB Output is correct
2 Correct 14 ms 23780 KB Output is correct
3 Correct 14 ms 23756 KB Output is correct
4 Correct 14 ms 23812 KB Output is correct
5 Correct 17 ms 23756 KB Output is correct
6 Correct 15 ms 23812 KB Output is correct
7 Incorrect 14 ms 23816 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 31492 KB Output is correct
2 Correct 64 ms 31048 KB Output is correct
3 Correct 63 ms 29464 KB Output is correct
4 Correct 67 ms 30280 KB Output is correct
5 Correct 75 ms 28868 KB Output is correct
6 Correct 59 ms 28812 KB Output is correct
7 Correct 60 ms 28484 KB Output is correct
8 Correct 62 ms 28688 KB Output is correct
9 Correct 59 ms 28164 KB Output is correct
10 Correct 71 ms 28404 KB Output is correct
11 Correct 54 ms 27716 KB Output is correct
12 Correct 52 ms 27648 KB Output is correct
13 Correct 49 ms 27588 KB Output is correct
14 Correct 53 ms 27572 KB Output is correct
15 Correct 41 ms 27224 KB Output is correct
16 Correct 40 ms 27152 KB Output is correct
17 Correct 15 ms 24140 KB Output is correct
18 Correct 15 ms 24180 KB Output is correct
19 Correct 16 ms 24140 KB Output is correct
20 Correct 15 ms 24196 KB Output is correct
21 Correct 15 ms 24176 KB Output is correct
22 Correct 15 ms 24204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 27724 KB Output is correct
2 Correct 19 ms 27724 KB Output is correct
3 Correct 17 ms 27744 KB Output is correct
4 Correct 15 ms 23800 KB Output is correct
5 Correct 19 ms 27788 KB Output is correct
6 Correct 19 ms 27788 KB Output is correct
7 Correct 18 ms 23792 KB Output is correct
8 Correct 17 ms 27688 KB Output is correct
9 Correct 18 ms 27788 KB Output is correct
10 Correct 18 ms 27792 KB Output is correct
11 Correct 17 ms 27672 KB Output is correct
12 Correct 17 ms 27724 KB Output is correct
13 Correct 16 ms 27724 KB Output is correct
14 Correct 17 ms 27724 KB Output is correct
15 Correct 16 ms 27740 KB Output is correct
16 Correct 16 ms 27664 KB Output is correct
17 Correct 18 ms 27824 KB Output is correct
18 Correct 16 ms 27724 KB Output is correct
19 Correct 17 ms 27788 KB Output is correct
20 Correct 19 ms 27792 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 32264 KB Output is correct
2 Correct 69 ms 32060 KB Output is correct
3 Correct 72 ms 32008 KB Output is correct
4 Correct 94 ms 32044 KB Output is correct
5 Correct 78 ms 32196 KB Output is correct
6 Correct 77 ms 29688 KB Output is correct
7 Correct 78 ms 34828 KB Output is correct
8 Correct 95 ms 34080 KB Output is correct
9 Correct 79 ms 33312 KB Output is correct
10 Correct 79 ms 32044 KB Output is correct
11 Correct 77 ms 32132 KB Output is correct
12 Correct 91 ms 32104 KB Output is correct
13 Correct 70 ms 32276 KB Output is correct
14 Correct 67 ms 32196 KB Output is correct
15 Correct 62 ms 31960 KB Output is correct
16 Correct 51 ms 31116 KB Output is correct
17 Correct 57 ms 32444 KB Output is correct
18 Correct 53 ms 32444 KB Output is correct
19 Correct 51 ms 32440 KB Output is correct
20 Correct 58 ms 32504 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 27792 KB Output is correct
2 Correct 16 ms 27724 KB Output is correct
3 Runtime error 775 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 78 ms 32716 KB Output is correct
2 Correct 75 ms 32400 KB Output is correct
3 Runtime error 934 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 Correct 14 ms 23704 KB Output is correct
2 Correct 14 ms 23780 KB Output is correct
3 Correct 14 ms 23756 KB Output is correct
4 Correct 14 ms 23812 KB Output is correct
5 Correct 17 ms 23756 KB Output is correct
6 Correct 15 ms 23812 KB Output is correct
7 Incorrect 14 ms 23816 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23704 KB Output is correct
2 Correct 14 ms 23780 KB Output is correct
3 Correct 14 ms 23756 KB Output is correct
4 Correct 14 ms 23812 KB Output is correct
5 Correct 17 ms 23756 KB Output is correct
6 Correct 15 ms 23812 KB Output is correct
7 Incorrect 14 ms 23816 KB Output isn't correct
8 Halted 0 ms 0 KB -