Submission #1168442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168442		zh_h	Island (NOI18_island)	C++20	100 / 100	266 ms	23188 KiB

island

#include <bits/stdc++.h>
#define pb push_back
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> edge_list(n+m+1);
    vector<bool> isLeaf(n+m+1, false);
    set<int> s;

    for (int i = 0; i < n+m-1; i ++) {
        int u, v;
        cin >> u >> v;

        edge_list[u].pb(v);
        edge_list[v].pb(u);

        if (u <= n) {isLeaf[u] = true; s.insert(v);}
        if (v <= n) {isLeaf[v] = true; s.insert(u);}
    }

    vector<int> ans;
    set<int> list_of_ans;
    map<int, int> cnt;
    int max_ans = 0;

    while (!s.empty()) {

        vector<int> parent_of_leaf;
        for (auto i : s) {parent_of_leaf.pb(i);}
        s.clear();
        
        for (int i = 0; i < parent_of_leaf.size(); i ++) {
            if (isLeaf[parent_of_leaf[i]]) {continue;}

            vector<int> notLeaf;
            for (auto j : edge_list[parent_of_leaf[i]]) {
                if (!isLeaf[j]) {notLeaf.pb(j);}
            }

            if (notLeaf.size() == 1) {
                isLeaf[parent_of_leaf[i]] = true;
                
                int new_ans = edge_list[parent_of_leaf[i]].size()-1;
                max_ans = max(max_ans, new_ans);
                cnt[new_ans] ++;
                
                s.insert(notLeaf[0]);
            }
            else if (notLeaf.size() == 0) {
                isLeaf[parent_of_leaf[i]] = true;

                int new_ans = edge_list[parent_of_leaf[i]].size()-1; // -1 is because of the "round table permutation problem"
                max_ans = max(max_ans, new_ans);
                cnt[new_ans] ++;
            }
        }
    }

    int ans_cnt = 0;
    for (int i = max_ans; i > 1; i --) {
        ans_cnt += cnt[i];
        cout << i << " " << ans_cnt << endl;
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31
• Subtask 4: 42 / 42