Submission #1090147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090147		Gourougourou	Untitled (POI11_kon)	C++17	100 / 100	1209 ms	131072 KiB

Main

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10