oj.uz

Submission #260891

# Submission time Handle Problem Language Result Execution time Memory
260891 2020-08-11T07:07:32 Z wiwiho Duathlon (APIO18_duathlon) C++14
8 / 100
 86 ms 8952 KB 
#include <bits/stdc++.h>

#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;

typedef long long ll;

const ll MAX = 2147483647;

vector<vector<int>> g;
vector<bool> vst;

ll sz = 0;
bool tmp = false;
void dfs(int now){
    vst[now] = true;
    sz++;
    if(g[now].size() == 1) tmp = true;
    for(int i : g[now]){
        if(!vst[i]) dfs(i);
    }
}

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

    int n, m;
    cin >> n >> m;

    g.resize(n + 1);
    vst.resize(n + 1);

    ll ans = 0;
    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        g[u].eb(v);
        g[v].eb(u);
    }

    for(int i = 1; i <= n; i++){
        if(vst[i]) continue;
        sz = 0;
        tmp = false;
        dfs(i);
        if(sz < 3) continue;
        if(tmp) ans += sz * (sz - 1) * (sz - 2) / 3;
        else ans += sz * (sz - 1) * (sz - 2);
    }

    cout << ans << "\n";

    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 288 KB Output is correct
7 Incorrect 1 ms 384 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 75 ms 8952 KB Output is correct
2 Correct 71 ms 8952 KB Output is correct
3 Correct 86 ms 7544 KB Output is correct
4 Correct 72 ms 8184 KB Output is correct
5 Correct 75 ms 6904 KB Output is correct
6 Correct 75 ms 6904 KB Output is correct
7 Correct 78 ms 6480 KB Output is correct
8 Correct 74 ms 6648 KB Output is correct
9 Correct 60 ms 6144 KB Output is correct
10 Correct 58 ms 6392 KB Output is correct
11 Correct 61 ms 5752 KB Output is correct
12 Correct 56 ms 5752 KB Output is correct
13 Correct 61 ms 5632 KB Output is correct
14 Correct 45 ms 5496 KB Output is correct
15 Correct 35 ms 5248 KB Output is correct
16 Correct 34 ms 5240 KB Output is correct
17 Correct 2 ms 2688 KB Output is correct
18 Correct 3 ms 2688 KB Output is correct
19 Correct 2 ms 2688 KB Output is correct
20 Correct 3 ms 2688 KB Output is correct
21 Correct 3 ms 2688 KB Output is correct
22 Correct 2 ms 2688 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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