Submission #1090145

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1090145	2024-09-17T20:07:47 Z	Gourougourou	Conspiracy (POI11_kon)	C++17	90 / 100	1143 ms	131072 KB

#include <iostream>
#include <bits/stdc++.h>

using namespace std;


int countAttackGroups(int N, int M, vector<int> A, vector<int> B) {
    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	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	344 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 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	452 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	456 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	380 KB	Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1116 KB	Output is correct
2	Correct	29 ms	8120 KB	Output is correct
3	Correct	147 ms	37392 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	1496 KB	Output is correct
2	Correct	41 ms	11180 KB	Output is correct
3	Correct	184 ms	49536 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	7948 KB	Output is correct
2	Correct	93 ms	24436 KB	Output is correct
3	Correct	332 ms	80212 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	13000 KB	Output is correct
2	Correct	222 ms	55748 KB	Output is correct
3	Correct	731 ms	131072 KB	Output is correct

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	524 ms	126216 KB	Output is correct
2	Correct	338 ms	82860 KB	Output is correct
3	Runtime error	1143 ms	131072 KB	Execution killed with signal 9
4	Halted	0 ms	0 KB	-

Submission #1090145

Compilation message