Submission #1277907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277907		sssukhpreet2003	어르신 집배원 (BOI14_postmen)	C++20	55 / 100	594 ms	146652 KiB

postmen

#include <bits/stdc++.h>

using namespace std;

void dfs(int root, vector<int> &ans, vector<set<int>> &g, vector<vector<int>> &res,vector<bool> &exists){
    while(g[root].size()){
        int next=*g[root].begin();
        g[next].erase(root);
        g[root].erase(next);
        dfs(next,ans,g,res,exists);
    }
    if(!exists[root]) {
        exists[root]=true;
        ans.push_back(root);
    }
    else{
        vector<int> temp;
        while(ans.back()!=root){
            temp.push_back(ans.back());
            exists[ans.back()]=false;
            ans.pop_back();
        }
        temp.push_back(ans.back());
        res.push_back(temp);
    }
}

int main(){
    int n,m;cin>>n>>m;
    vector<set<int>> g(n+1);
    vector<int> deg(n+1);
    vector<int> ans;
    vector<vector<int>> res;
    vector<bool> exists(n+1);
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        g[a].insert(b);
        g[b].insert(a);
        deg[a]++;
        deg[b]++;
    }
    // for(int i=0;i<n+1;i++) if(deg[i]%2) {cout<<"IMPOSSIBLE"<<endl; return 0;}
    dfs(1,ans,g,res,exists);
    // if(ans.size()!=m+1) {cout<<"IMPOSSIBLE"<<endl; return 0;}
    // for(int i=ans.size()-1;i>=0;i--) cout<<ans[i]<<" ";
    // cout<<endl;

    for(int i=0;i<res.size();i++){
        for(int j=0;j<res[i].size();j++){
            cout<<res[i][j]<<" ";
        }cout<<endl;
    }
return 0;
}

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