Submission #217983

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
217983	2020-03-31T11:35:46 Z	Vimmer	Duathlon (APIO18_duathlon)	C++14	23 / 100	1000 ms	1048580 KB

count_triplets

#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)
{
    mkr[v] = 1;

    kol++;

    bool f = 0;

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

            if (it == i) f = 1;
              else if (!mkr[it]) 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 && m <= 100)
    {
        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 += max(0ll, kol * (kol - 1) * (kol - 2)); 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	6 ms	2688 KB	Output is correct
4	Correct	6 ms	2688 KB	Output is correct
5	Correct	7 ms	2688 KB	Output is correct
6	Correct	6 ms	2688 KB	Output is correct
7	Correct	7 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	540 ms	2688 KB	Output is correct
11	Correct	6 ms	2688 KB	Output is correct
12	Correct	7 ms	2720 KB	Output is correct
13	Correct	7 ms	2688 KB	Output is correct
14	Correct	7 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	7 ms	2688 KB	Output is correct
19	Correct	7 ms	2688 KB	Output is correct
20	Runtime error	590 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	6 ms	2688 KB	Output is correct
4	Correct	6 ms	2688 KB	Output is correct
5	Correct	7 ms	2688 KB	Output is correct
6	Correct	6 ms	2688 KB	Output is correct
7	Correct	7 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	540 ms	2688 KB	Output is correct
11	Correct	6 ms	2688 KB	Output is correct
12	Correct	7 ms	2720 KB	Output is correct
13	Correct	7 ms	2688 KB	Output is correct
14	Correct	7 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	7 ms	2688 KB	Output is correct
19	Correct	7 ms	2688 KB	Output is correct
20	Runtime error	590 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	76 ms	10592 KB	Output is correct
2	Correct	91 ms	11768 KB	Output is correct
3	Execution timed out	1120 ms	411328 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	6 ms	2816 KB	Output is correct
6	Correct	6 ms	2816 KB	Output is correct
7	Correct	6 ms	2816 KB	Output is correct
8	Correct	6 ms	2816 KB	Output is correct
9	Correct	6 ms	2816 KB	Output is correct
10	Correct	6 ms	2944 KB	Output is correct
11	Correct	6 ms	2688 KB	Output is correct
12	Correct	6 ms	2688 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	2816 KB	Output is correct
18	Correct	7 ms	2816 KB	Output is correct
19	Correct	6 ms	2688 KB	Output is correct
20	Correct	6 ms	2816 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	68 ms	6904 KB	Output is correct
2	Correct	59 ms	6776 KB	Output is correct
3	Correct	58 ms	6776 KB	Output is correct
4	Correct	61 ms	6776 KB	Output is correct
5	Correct	57 ms	6776 KB	Output is correct
6	Correct	76 ms	10104 KB	Output is correct
7	Correct	89 ms	9080 KB	Output is correct
8	Correct	68 ms	8440 KB	Output is correct
9	Correct	70 ms	7788 KB	Output is correct
10	Correct	57 ms	6776 KB	Output is correct
11	Correct	74 ms	6780 KB	Output is correct
12	Correct	56 ms	6776 KB	Output is correct
13	Correct	60 ms	6776 KB	Output is correct
14	Correct	51 ms	6636 KB	Output is correct
15	Correct	45 ms	6520 KB	Output is correct
16	Correct	31 ms	5888 KB	Output is correct
17	Correct	40 ms	7152 KB	Output is correct
18	Correct	54 ms	7152 KB	Output is correct
19	Correct	40 ms	7276 KB	Output is correct
20	Correct	38 ms	7168 KB	Output is correct

Subtask #6
0 / 15.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	Runtime error	701 ms	1048580 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	58 ms	6776 KB	Output is correct
2	Correct	63 ms	6776 KB	Output is correct
3	Runtime error	862 ms	1048580 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
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	6 ms	2688 KB	Output is correct
4	Correct	6 ms	2688 KB	Output is correct
5	Correct	7 ms	2688 KB	Output is correct
6	Correct	6 ms	2688 KB	Output is correct
7	Correct	7 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	540 ms	2688 KB	Output is correct
11	Correct	6 ms	2688 KB	Output is correct
12	Correct	7 ms	2720 KB	Output is correct
13	Correct	7 ms	2688 KB	Output is correct
14	Correct	7 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	7 ms	2688 KB	Output is correct
19	Correct	7 ms	2688 KB	Output is correct
20	Runtime error	590 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	6 ms	2688 KB	Output is correct
4	Correct	6 ms	2688 KB	Output is correct
5	Correct	7 ms	2688 KB	Output is correct
6	Correct	6 ms	2688 KB	Output is correct
7	Correct	7 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	540 ms	2688 KB	Output is correct
11	Correct	6 ms	2688 KB	Output is correct
12	Correct	7 ms	2720 KB	Output is correct
13	Correct	7 ms	2688 KB	Output is correct
14	Correct	7 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	7 ms	2688 KB	Output is correct
19	Correct	7 ms	2688 KB	Output is correct
20	Runtime error	590 ms	1048580 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
21	Halted	0 ms	0 KB	-

Submission #217983

Compilation message