oj.uz

Submission #371171

# Submission time Handle Problem Language Result Execution time Memory
371171 2021-02-26T03:36:54 Z two_sides Conspiracy (POI11_kon) C++17
100 / 100
 1950 ms 117596 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 5005;

int deg[N], cnt[N], val[N];

int getC(int n, int k) {
    k = min(k, n - k);
    int res = 1;
    for (int i = 1; i <= k; i++)
        res = res * (n - k + i) / i;
    return res;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> deg[i]; int u;
        for (int j = 0; j < deg[i]; j++) cin >> u;
        cnt[deg[i]]++;
    }
    for (int i = n - 1; i >= 0; i--)
        cnt[i] += cnt[i + 1];
    for (int i = 1; i <= n; i++)
        val[cnt[deg[i]]--] = deg[i];
    int tot = 0, cur = 0, sum = 0, res = 0;
    for (int i = 1; i <= n; i++) cnt[i] = 0;
    for (int i = 1; i <= n; i++) {
        cnt[val[i]]++; tot += val[i];
    }
    for (int i = 1; i < n; i++) {
        sum += val[i];
        if (val[i] != val[i - 1]) cur = 1;
        else cur++;
        if (sum * 2 == i * (i - 1) + tot)
            res += getC(cnt[val[i]], cur);
    }
    cout << res << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 620 KB Output is correct
2 Correct 49 ms 3052 KB Output is correct
3 Correct 233 ms 13420 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 876 KB Output is correct
2 Correct 70 ms 4204 KB Output is correct
3 Correct 312 ms 18028 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 3180 KB Output is correct
2 Correct 159 ms 9196 KB Output is correct
3 Correct 501 ms 29548 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 5376 KB Output is correct
2 Correct 348 ms 20972 KB Output is correct
3 Correct 1163 ms 69740 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 789 ms 47980 KB Output is correct
2 Correct 530 ms 31516 KB Output is correct
3 Correct 1808 ms 108012 KB Output is correct
4 Correct 1950 ms 117596 KB Output is correct
5 Correct 1 ms 364 KB Output is correct