Submission #1242496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242496		minhpk	Senior Postmen (BOI14_postmen)	C++20	0 / 100	18 ms	27460 KiB

postmen

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector <pair<int,int>> z[1000005];
bool del[1000005];
bool vis[1000005];
stack<int> st;
vector <vector<int>> res;
int sl[1000005];
int cur[1000005];

void dfs(int i){
    vis[i]=true;
    st.push(i);
    for (auto p:z[i]){
         if (del[p.second]){
            continue;
         }
         del[p.second]=true;
         cur[i]++;
         cur[p.first]++;
        // cout << i << " " << p.first << "\n";
         if (!vis[p.first]){
             dfs(p.first);
         }else{
             int v=0;
             vector <int> pre;
             while (v!=p.first){
                  v=st.top();
                  vis[v]=false;
                  st.pop();
                  pre.push_back(v);
             }
             res.push_back(pre);
            // cout << v << "\n";
             dfs(v);
         }
    }
    if (st.size()==1){
        st.pop();
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a,b;
    cin >> a >> b;
    for (int i=1;i<=b;i++){
         int x,y;
         cin >> x >> y;
         z[x].push_back({y,i});
         z[y].push_back({x,i});
         sl[x]++;
         sl[y]++;
    }
    vector <int> pre;
    for (int i=1;i<=a;i++){
        if (cur[i]!=sl[i]){
//            cout << i << "\n";
            dfs(i);
        }
//        if (i==7){
//            cout << cur[i] << " " << sl[i] << "\n";
//        }
    }
    while (st.size()){
        pre.push_back(st.top());
        st.pop();
    }
    res.push_back(pre);
//    cout << "\n";
    for (auto c:res){
         for (auto p:c){
             cout << p << " ";
         }
         cout << "\n";
    }
    return 0;
}

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