Submission #1230603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230603		enzy	Senior Postmen (BOI14_postmen)	C++20	38 / 100	831 ms	53440 KiB

postmen

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
map<pair<int,int>,int>marc;
vector<int>v[maxn], cycle, resp[maxn];
int last[maxn];
void dfs(int u){
    while(!v[u].empty()){
        int a=v[u].back();
        v[u].pop_back();
        if(marc[{u,a}]==1) continue;
        marc[{u,a}]=marc[{a,u}]=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); v[b].push_back(a);
    }
    dfs(1);
    memset(last,-1,sizeof(last));
    //for(int a : cycle) cout << a << " ";
    //cout << endl;
    for(int i=0;i<cycle.size();i++){
        if(last[cycle[i]]!=-1){
            //cout << i << ": ";
            for(int j=last[cycle[i]];j<i;j++){
                if(cycle[j]!=-1) cout << cycle[j] << " ";
                if(cycle[j]!=-1) last[cycle[j]]=-1;
                cycle[j]=-1;
            }
            cout << endl;
        }
        last[cycle[i]]=i;
    }
    //for(int a : cycle) if(a!=-1) cout << a << " ";
    //cout << endl;
}

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