Submission #1229157

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229157		jakeob77	Senior Postmen (BOI14_postmen)	C++17	100 / 100	354 ms	70432 KiB

postmen

#include <bits/stdc++.h>
#include <cstdint>
using namespace std;
#define ll long long
#define pb push_back
#define ins insert
//cout<<fixed<<setprecision(3); 3 decimalke brez fixed pa 3 zanesljiva mesta
const int MAXN=1e6+3;
const long long linf=1e18;
const int inf=1e9;
const int mod=1e9+7;
vector<int>res;
vector<vector<pair<int,int>>>adj;
vector<int>vis;
vector<int>in;

void dfs(int e){
    while(adj[e].size()){
        auto ne=adj[e].back();
        adj[e].pop_back();
        if(vis[ne.second]) continue;
        vis[ne.second]++;
        dfs(ne.first);
    }
    if(in[e]){
        cout<<e+1<<' ';
        in[e]--;
        while(res.back()!=e+1){
            cout<<res.back()<<' ';
            in[res.back()-1]--;
            res.pop_back();
        }
        res.pop_back();
        cout<<endl;
    }
    res.pb(e+1);
    in[e]++;
}

void solve(){
    int n,m;cin>>n>>m;
    adj=vector<vector<pair<int,int>>>(n);
    vector<int>deg(n,0);
    vis=vector<int>(m,0);

    in=vector<int>(n,0);
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        --a;--b;
        adj[a].pb({b,i});
        adj[b].pb({a,i});
        deg[a]++;
        deg[b]++;
    }
    bool ok=true;
    for(int i=0;i<n;i++){
        if(deg[i]&1) ok=false;
    }
    dfs(0);
    if(!ok){
        cout<< "IMPOSSIBLE"<<endl;
    }
    else{
    }
}  

int main(){
    std::ios::sync_with_stdio(false);
	std::cin.tie(NULL); 
    int t=1;
    while(t--) solve();
    
}

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