Submission #1230605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230605		enzy	Senior Postmen (BOI14_postmen)	C++20	100 / 100	280 ms	64472 KiB

postmen

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
vector<pair<int,int>> v[maxn];
vector<int> cycle;
int last[maxn], l[maxn], r[maxn], marc[maxn];
void dfs(int u){
    while(!v[u].empty()){
        int a=v[u].back().first, id=v[u].back().second;
        v[u].pop_back();
        if(marc[id]) continue;
        marc[id]=1;
        dfs(a);
    }
    cycle.push_back(u);
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, m; cin >> n >> m;
    for(int i=1;i<=m;i++){
        int a, b; cin >> a >> b;
        v[a].push_back({b,i}); v[b].push_back({a,i});
    }
    dfs(1);
    memset(last,-1,sizeof(last));
    for(int i=1;i<cycle.size()-1;i++){
        l[i]=i-1; r[i]=i+1;
    }
    r[0]=1; 
    if(cycle.size()>=2) l[cycle.size()-1]=cycle.size()-2; 
    for(int i=0;i<cycle.size();i++){
        if(last[cycle[i]]!=-1){
            int j=last[cycle[i]], at=l[j];
            while(j<i){
                cout << cycle[j] << " ";
                last[cycle[j]]=-1;
                cycle[j]=-1;
                j=r[j];
            }
            r[at]=j; l[j]=at;
            cout << endl;
        }
        last[cycle[i]]=i;
    }
}

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