Submission #1048017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048017		luanzito	Senior Postmen (BOI14_postmen)	C++14	100 / 100	275 ms	128244 KiB

postmen

#include <bits/stdc++.h>
#define int long long 
#define pb push_back
#define fr first
#define sc second
#define bg begin()
#define ed end()
#define lf(no) no << 1
#define rg(no) lf(no) | 1
#define lsb(x) x & (-x)
#define all(x) x.begin(),x.end()
#define sz(x) (int) x.size()
#define debug(x) cout << x << endl;
 
using namespace std;
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
 
const int maxn = 5e5 + 10;
 
int n,m,t,qtd[maxn],mark[maxn],mv[maxn];
vector<int> resp[maxn],id[maxn];
stack<int> p;
pii e[maxn];
 
void find(int u){
    
    if(mv[u]){
        t++;
        int v;
        do{
            v = p.top();
            p.pop();
            mv[v]--;
            resp[t].pb(v);
        }while(v != u);
    }
    
    while(sz(id[u])){
        int ind = id[u].back();
        if(mark[ind]){
            id[u].pop_back();
            continue;
        }
        
        mark[ind] = 1;
        int v = e[ind].fr + e[ind].sc - u;
        id[u].pop_back();
        mv[u]++;
        p.push(u);
        find(v);
        
    }

}
 
void solve(){
    
    cin >> n >> m;
    
    for(int i = 1;i <= m;i++){
        int u,v;
        cin >> u >> v;
        e[i] = {u,v};
        id[u].pb(i);
        id[v].pb(i);
    }
    
    find(1);
    
    for(int i = 1;i <= t;i++){
        for(int v : resp[i])
            cout << v << " ";
        cout << "\n";
    }

}
 
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while(t--)
        solve();
    return 0;
}

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