oj.uz

Submission #217970

# Submission time Handle Problem Language Result Execution time Memory
217970 2020-03-31T11:23:06 Z Vimmer Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 1048580 KB 
#include <bits/stdc++.h>

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 100005
#define M ll(998244353)

using namespace std;

typedef long double ld;
typedef long long ll;
typedef short int si;


vector <int> g[N];

bool mk[N], mkr[N];

int i, j, n, m;

ll anser, siz[N], kol;

void calc(int v, int p)
{
    if (p != -1) {siz[p] -= siz[v]; siz[v] += siz[p];}

    for (auto it : g[v]) anser += (siz[v] - 1 - siz[it]) * siz[it];

    for (auto it : g[v]) {if (p == it) continue; calc(it, v);}

    if (p != -1) {siz[v] -= siz[p]; siz[p] += siz[v];}
}

void dfs(int v, int p)
{
    mkr[v] = 1;

    siz[v] = 0;

    for (auto it : g[v])
    {
        if (it == p) continue;

        dfs(it, v);

        siz[v] += siz[it];
    }

    siz[v]++;

    if (i == v) calc(v, -1);
}


bool dostig(int v, int to)
{
    if (mk[v]) return 0;

    if (v == to) return 1;

    mk[v] = 1;

    bool f = 0;

    for (auto it : g[v]) f |= dostig(it, to);

    mk[v] = 0;

    if (f && v != i && !mkr[v]) {mkr[v] = 1; anser++;}

    return f;
}

bool opr(int v, int p)
{
    mk[v] = 1;

    kol++;

    bool f = 0;

    for (auto it : g[v])
        {
            if (it == p) continue;

            if (mk[it]) f = 1;
              else f |= opr(it, v);
        }
    return f;
}
int main()
{
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        int x, y;

        cin >> x >> y;

        g[x].pb(y);

        g[y].pb(x);
    }

    if (m <= n - 1)
    {
        for (i = 1; i <= n; i++) if (siz[i] == 0) dfs(i, -1);
    }
    else

    if (n <= 10)
    {
        for (i = 1; i <= n; i++)
          for (j = 1; j <= n; j++)
            if (i != j){for (int u = 0; u < 51; u++) mkr[u] = 0; dostig(i, j);}
    }
    else
    {
        for (i = 1; i <= n; i++)
        {
            if (mkr[i]) continue;

            kol = 0;

            if (opr(i, -1))
            {
                anser += kol * (kol - 1) * (kol - 2);

                continue;
            }
            else dfs(i, -1);
        }
    }

    cout << anser << endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 7 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 7 ms 2748 KB Output is correct
7 Correct 6 ms 2688 KB Output is correct
8 Correct 7 ms 2688 KB Output is correct
9 Correct 27 ms 2688 KB Output is correct
10 Correct 564 ms 2744 KB Output is correct
11 Correct 6 ms 2688 KB Output is correct
12 Correct 6 ms 2688 KB Output is correct
13 Correct 7 ms 2688 KB Output is correct
14 Correct 6 ms 2688 KB Output is correct
15 Correct 6 ms 2688 KB Output is correct
16 Correct 6 ms 2688 KB Output is correct
17 Correct 6 ms 2688 KB Output is correct
18 Correct 6 ms 2688 KB Output is correct
19 Correct 6 ms 2688 KB Output is correct
20 Runtime error 554 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 7 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 7 ms 2748 KB Output is correct
7 Correct 6 ms 2688 KB Output is correct
8 Correct 7 ms 2688 KB Output is correct
9 Correct 27 ms 2688 KB Output is correct
10 Correct 564 ms 2744 KB Output is correct
11 Correct 6 ms 2688 KB Output is correct
12 Correct 6 ms 2688 KB Output is correct
13 Correct 7 ms 2688 KB Output is correct
14 Correct 6 ms 2688 KB Output is correct
15 Correct 6 ms 2688 KB Output is correct
16 Correct 6 ms 2688 KB Output is correct
17 Correct 6 ms 2688 KB Output is correct
18 Correct 6 ms 2688 KB Output is correct
19 Correct 6 ms 2688 KB Output is correct
20 Runtime error 554 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 11000 KB Output is correct
2 Correct 68 ms 10872 KB Output is correct
3 Execution timed out 1122 ms 416500 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2816 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 7 ms 2816 KB Output is correct
5 Correct 7 ms 2816 KB Output is correct
6 Correct 6 ms 2816 KB Output is correct
7 Correct 7 ms 2816 KB Output is correct
8 Correct 7 ms 2944 KB Output is correct
9 Correct 6 ms 2816 KB Output is correct
10 Correct 6 ms 2688 KB Output is correct
11 Correct 6 ms 2688 KB Output is correct
12 Correct 6 ms 2816 KB Output is correct
13 Correct 6 ms 2688 KB Output is correct
14 Correct 6 ms 2688 KB Output is correct
15 Correct 6 ms 2688 KB Output is correct
16 Correct 6 ms 2688 KB Output is correct
17 Correct 6 ms 2688 KB Output is correct
18 Correct 6 ms 2816 KB Output is correct
19 Correct 6 ms 2688 KB Output is correct
20 Correct 6 ms 2688 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 7032 KB Output is correct
2 Correct 64 ms 7032 KB Output is correct
3 Correct 59 ms 7032 KB Output is correct
4 Correct 66 ms 7032 KB Output is correct
5 Correct 74 ms 7160 KB Output is correct
6 Correct 85 ms 10360 KB Output is correct
7 Correct 81 ms 9208 KB Output is correct
8 Correct 73 ms 8696 KB Output is correct
9 Correct 78 ms 8056 KB Output is correct
10 Correct 65 ms 7032 KB Output is correct
11 Correct 69 ms 7032 KB Output is correct
12 Correct 57 ms 7032 KB Output is correct
13 Correct 62 ms 7032 KB Output is correct
14 Correct 53 ms 6904 KB Output is correct
15 Correct 53 ms 6776 KB Output is correct
16 Correct 31 ms 6136 KB Output is correct
17 Correct 45 ms 7408 KB Output is correct
18 Correct 43 ms 7412 KB Output is correct
19 Correct 49 ms 7404 KB Output is correct
20 Correct 43 ms 7416 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 7032 KB Output is correct
2 Correct 62 ms 7032 KB Output is correct
3 Incorrect 74 ms 6624 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 7 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 7 ms 2748 KB Output is correct
7 Correct 6 ms 2688 KB Output is correct
8 Correct 7 ms 2688 KB Output is correct
9 Correct 27 ms 2688 KB Output is correct
10 Correct 564 ms 2744 KB Output is correct
11 Correct 6 ms 2688 KB Output is correct
12 Correct 6 ms 2688 KB Output is correct
13 Correct 7 ms 2688 KB Output is correct
14 Correct 6 ms 2688 KB Output is correct
15 Correct 6 ms 2688 KB Output is correct
16 Correct 6 ms 2688 KB Output is correct
17 Correct 6 ms 2688 KB Output is correct
18 Correct 6 ms 2688 KB Output is correct
19 Correct 6 ms 2688 KB Output is correct
20 Runtime error 554 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 7 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 7 ms 2748 KB Output is correct
7 Correct 6 ms 2688 KB Output is correct
8 Correct 7 ms 2688 KB Output is correct
9 Correct 27 ms 2688 KB Output is correct
10 Correct 564 ms 2744 KB Output is correct
11 Correct 6 ms 2688 KB Output is correct
12 Correct 6 ms 2688 KB Output is correct
13 Correct 7 ms 2688 KB Output is correct
14 Correct 6 ms 2688 KB Output is correct
15 Correct 6 ms 2688 KB Output is correct
16 Correct 6 ms 2688 KB Output is correct
17 Correct 6 ms 2688 KB Output is correct
18 Correct 6 ms 2688 KB Output is correct
19 Correct 6 ms 2688 KB Output is correct
20 Runtime error 554 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -