oj.uz

Submission #1090147

# Submission time Handle Problem Language Result Execution time Memory
1090147 2024-09-17T20:13:59 Z Gourougourou Conspiracy (POI11_kon) C++17
100 / 100
 1209 ms 131072 KB 
#include <iostream>
#include <bits/stdc++.h>

using namespace std;


int countAttackGroups(int N, int M, vector<int> &A, vector<int> &B) {
    if (M == 0) return N;
    vector<int> deg(N), count(N);
    for (int i = 0; i<M; ++i) {
        ++deg[A[i]-1];
        ++deg[B[i]-1];
    }
    for (int i = 0; i<N; ++i) ++count[deg[i]];
    sort(deg.begin(), deg.end(), greater<>());
    int sumDeg = 0, ans = 0;
    for (int i = 0; i<N-1; ++i) {
        sumDeg += deg[i];
        if (sumDeg - (i * (i+1)) / 2 == M) {
            if (deg[i] == deg[i+1]) ans += count[deg[i]];
            else ++ans;
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N;
    cin >> N;
    vector<int> A,B;
    A.reserve((N*(N-1))/2);
    B.reserve((N*(N-1))/2);
    for (int i = 1; i<=N; ++i) {
        int sz,a; cin >> sz;
        while (sz--) {
            cin >> a;
            if (a > i) {
                A.push_back(a);
                B.push_back(i);
            }
        }

    }
    cout << countAttackGroups(N, A.size(), A, B);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 856 KB Output is correct
2 Correct 32 ms 5380 KB Output is correct
3 Correct 137 ms 24660 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1112 KB Output is correct
2 Correct 41 ms 7436 KB Output is correct
3 Correct 187 ms 33104 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5460 KB Output is correct
2 Correct 92 ms 16668 KB Output is correct
3 Correct 301 ms 53324 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 9300 KB Output is correct
2 Correct 218 ms 37072 KB Output is correct
3 Correct 688 ms 126948 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 84220 KB Output is correct
2 Correct 307 ms 55636 KB Output is correct
3 Correct 1075 ms 131072 KB Output is correct
4 Correct 1209 ms 131072 KB Output is correct
5 Correct 1 ms 348 KB Output is correct