Submission #926607

#	Time	Username	Problem	Language	Result	Execution time	Memory
926607		vjudge1	Untitled (POI11_imp)	C++17	100 / 100	1209 ms	58528 KiB

Main

    #include <bits/stdc++.h>
    using namespace std;
     
    const int mxN = 5007;
     
    vector<int> g[mxN];
     
    int32_t main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        
        int n, m;
        cin >> n >> m;
     
        for (int i = 0; i < m; ++i) {
            int u, v;
            cin >> u >> v;
     
            g[u].push_back(v);
            g[v].push_back(u);
        }
        
        set<int> left;
        left.clear();
        for (int u = 1; u <= n; ++u) {
            left.insert(u);
        }
     
        for (int u = 1; u <= n; ++u) {
            if (!left.count(u)) {
                continue;
            }
     
            set<int> check = {u};
            for (auto v : g[u]) {
                check.insert(v);
            }
     
            for (int v = 1; v <= n; ++v) {
                if (!check.count(v) && left.count(v)) {
                    left.erase(u);
                    left.erase(v);
                    break;
                }
            }
        }
        
        if ((int)left.size() < n / 3) {
            cout << "1" << "\n";
            return 0;
        }
        auto it = left.begin();
        for (int i = 0; i < n / 3; ++i) {
            cout << *it << ' ';
            ++it;
        }
        cout << "\n";
    }

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 10 / 10