oj.uz

Submission #886401

# Submission time Handle Problem Language Result Execution time Memory
886401 2023-12-12T03:33:40 Z anhphant Duathlon (APIO18_duathlon) C++14
8 / 100
 39 ms 22356 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'

int inN, inM;
vector<int> inGR[100007];

void initialize() {
    ios_base :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0); cerr.tie(0);
    if (fopen("FILE.INP", "r")) {
        freopen("FILE.INP", "r", stdin);
        freopen("FILE.OUT", "w", stdout);
    }

    cin >> inN >> inM;
    for(int i = 1, u, v; i <= inM; ++i) {
        cin >> u >> v;
        inGR[u].push_back(v);
        inGR[v].push_back(u);
    }
}

int type_determine() {
    if (inN == 10) return 1;
    if (inN == 50) return 2;
}

namespace subtask1 {
    int N, M;
    bool havepath[17][17][17], visited[17];
    vector<int> GR[100007];
    ll ans = 0;

    void backtrack2(ll finish, ll mid, ll start) {
        if (finish != mid) {
            havepath[start][mid][finish] = 1;
        }

        for(int nxtfinish : GR[finish]) {
            if (visited[nxtfinish]) continue;
            visited[nxtfinish] = 1;
            backtrack2(nxtfinish, mid, start);
            visited[nxtfinish] = 0;
        }
    }

    void backtrack(ll mid, ll start) {
        if (mid != start) {
            backtrack2(mid, mid, start);
        }

        for(int nxtmid : GR[mid]) {
            if (visited[nxtmid]) continue;
            visited[nxtmid] = 1;
            backtrack(nxtmid, start);
            visited[nxtmid] = 0;
        }
    }

    void preprocess() {
        N = inN;
        M = inM;
        for(int i = 1; i <= N; ++i) GR[i] = inGR[i];
    }

    void solve() {
        for(int i = 1; i <= N; ++i) {
            visited[i] = 1;
            backtrack(i, i);
            visited[i] = 0;
        }

        for(int i = 1; i <= N; ++i) {
            for(int j = 1; j <= N; ++j) {
                for(int k = 1; k <= N; ++k) {
                    ans += havepath[i][j][k];
                }
            }
        }

        cout << ans << endl;
    }

    void process() {
        preprocess();
        solve();
    }
}

namespace subtask3 {
    int N, M, CpnCnt, cpn[100007], sz[100007], type[100007];
    vector<int> GR[100007];

    void preprocess() {
        N = inN;
        M = inM;
        for(int i = 1; i <= N; ++i) GR[i] = inGR[i];
    }

    void Dfs(ll u, ll last) {
        cpn[u] = CpnCnt;
        for(int v : GR[u]) {
            if (v == last) continue;
            if (!cpn[v]) Dfs(v, u);
            else type[CpnCnt] = 1;
        }
    }

    void solve() {
        for(int i = 1; i <= N; ++i) {
            if (!cpn[i]) {
                CpnCnt++;
                Dfs(i, 0);
            }
        }

        for(int i = 1; i <= N; ++i) {
            sz[cpn[i]]++;
        }

        ll ans = 0;

        for(int i = 1; i <= CpnCnt; ++i) {
            ll k = sz[i];
            //cerr << i << " " << k << endl;
            if (!type[i]) ans += (k * (k - 1) * (k - 2)) / 6;
            else ans += ((k - 1) * (k - 2)) / 2 * k;
        }

        cout << ans * 2;
    }

    void process() {
        preprocess();
        solve();
    }
}

int main() {
    initialize();

    subtask3 :: process();

//    cout << 10 << " " << (100 * 99) / 2 << endl;
//    for(int i = 1; i <= 100; ++i) {
//        for(int j = 1; j <= i - 1; ++j) {
//            cout << i << " " << j << endl;
//        }
//    }
}

Compilation message

count_triplets.cpp: In function 'void initialize()':
count_triplets.cpp:13:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         freopen("FILE.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:14:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         freopen("FILE.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int type_determine()':
count_triplets.cpp:28:1: warning: control reaches end of non-void function [-Wreturn-type]
   28 | }
      | ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 3 ms 8676 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Incorrect 2 ms 8540 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 3 ms 8676 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Incorrect 2 ms 8540 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 37 ms 21072 KB Output is correct
2 Correct 36 ms 22356 KB Output is correct
3 Correct 36 ms 19216 KB Output is correct
4 Correct 38 ms 20620 KB Output is correct
5 Correct 32 ms 18260 KB Output is correct
6 Correct 33 ms 18252 KB Output is correct
7 Correct 33 ms 17232 KB Output is correct
8 Correct 34 ms 17796 KB Output is correct
9 Correct 33 ms 16720 KB Output is correct
10 Correct 35 ms 17228 KB Output is correct
11 Correct 29 ms 15708 KB Output is correct
12 Correct 28 ms 15708 KB Output is correct
13 Correct 25 ms 15440 KB Output is correct
14 Correct 25 ms 15188 KB Output is correct
15 Correct 22 ms 14420 KB Output is correct
16 Correct 21 ms 14296 KB Output is correct
17 Correct 4 ms 8728 KB Output is correct
18 Correct 3 ms 8540 KB Output is correct
19 Correct 3 ms 8536 KB Output is correct
20 Correct 3 ms 8680 KB Output is correct
21 Correct 3 ms 8540 KB Output is correct
22 Correct 3 ms 8540 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 14940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 8536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 14804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 3 ms 8676 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Incorrect 2 ms 8540 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 3 ms 8676 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Incorrect 2 ms 8540 KB Output isn't correct
8 Halted 0 ms 0 KB -