Submission #1277909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277909		sssukhpreet2003	Senior Postmen (BOI14_postmen)	C++20	100 / 100	485 ms	107680 KiB

postmen

#include <bits/stdc++.h>

using namespace std;

void dfs(int root, vector<int> &ans, vector<vector<pair<int,int>>> &g, vector<vector<int>> &res,vector<bool> &exists,vector<bool> &seen){
    while(g[root].size()){
        auto pr=g[root].back();
        g[root].pop_back();
        int next=pr.first;
        int ind=pr.second;
        if(seen[ind]) continue;
        seen[ind]=true;
        dfs(next,ans,g,res,exists,seen);
    }
    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<vector<pair<int,int>>> g(n+1);
    vector<int> deg(n+1);
    vector<int> ans;
    vector<vector<int>> res;
    vector<bool> exists(n+1);
    vector<bool> seen(m,false);
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        g[a].push_back(make_pair(b,i));
        g[b].push_back(make_pair(a,i));
        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,seen);
    // 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: 45 / 45