제출 #1141301

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141301		KindaGoodGames	어르신 집배원 (BOI14_postmen)	C++17	100 / 100	307 ms	33480 KiB

postmen

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

#define ll long long
#define pii pair<int,int>
#define tiii tuple<int,int,int>

using namespace std;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
        
    vector<bool> used(m);
    vector<vector<pii>> adj(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        adj[a].push_back({ b,i });
        adj[b].push_back({ a,i });
    } 
    vector<bool> occ(n);
    vector<bool> left(n,1); 
    stack<int> S;
    S.push(0);
    int pt = 0;
    while (S.size()) {
        int v = S.top();
        while (adj[v].size() && used[adj[v][0].second]) {
            swap(adj[v][0], adj[v][adj[v].size() - 1]);
            adj[v].pop_back();
        }
        if (adj[v].size() == 0) left[v] = false;
        if (occ[v]) {   
            cout << S.top() + 1 << " ";
            S.pop();
            do {
                cout << S.top() + 1 << " ";
                occ[S.top()] = false;  S.pop();
            } while (S.top() != v);
            cout << "\n"; 
            if (adj[S.top()].size() == 0) {
                S.pop();
            }
            while (pt < n) { 

                while (adj[pt].size() && used[adj[pt][0].second]) {
                    swap(adj[pt][0], adj[pt][adj[pt].size() - 1]);
                    adj[pt].pop_back();
                }
                if (adj[pt].empty())pt++;
                else break;
            }
            if (S.empty() && pt < left.size()) {
                S.push(pt);
            }
            if (S.empty()) break;
        }

        v = S.top();
        // as long as we have an invalid edge
        if (!adj[v].size()) break;
        // use an edge
        used[adj[v][0].second] = true;
        int u = adj[v][0].first;

        // erasur 
        swap(adj[v][0], adj[v][adj[v].size() - 1]);
        adj[v].pop_back();


        if (adj[v].size() == 0) left[v] = false;
        if (adj[u].size() == 0) left[u] = false;
        S.push(u);
        occ[v] = true;
    }  
    pt++;

}

• Subtask 1: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 45 / 45