oj.uz

Submission #1090146

# Submission time Handle Problem Language Result Execution time Memory
1090146 2024-09-17T20:08:42 Z Gourougourou Conspiracy (POI11_kon) C++17
90 / 100
 1164 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;
    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 1 ms 348 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 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 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 348 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 600 KB Output is correct
2 Correct 2 ms 768 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 3 ms 860 KB Output is correct
2 Correct 29 ms 5580 KB Output is correct
3 Correct 140 ms 24200 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1236 KB Output is correct
2 Correct 41 ms 7432 KB Output is correct
3 Correct 181 ms 31732 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 5252 KB Output is correct
2 Correct 95 ms 15772 KB Output is correct
3 Correct 309 ms 51044 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 8372 KB Output is correct
2 Correct 220 ms 35168 KB Output is correct
3 Correct 768 ms 131072 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 78724 KB Output is correct
2 Correct 313 ms 52308 KB Output is correct
3 Runtime error 1164 ms 131072 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -