Submission #1116408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116408		Sofiatpc	Senior Postmen (BOI14_postmen)	C++14	0 / 100	18 ms	39248 KiB

postmen

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define sc second
#define sz(v) (int)v.size()
struct back_edge{
    int d, v, id;
    bool operator<(const back_edge& b) const{
        return d < b.d;
    }
};
const int MAXN = 5*1e5+5;
vector< pair<int,int> > adj[MAXN];
set< back_edge > be[MAXN];
vector<int> cur;
int dist[MAXN], p[MAXN], marc[MAXN];

void dfsIni(int s){
    for(int i = 0; i < sz(adj[s]); i++){
        int viz = adj[s][i].fi, id = adj[s][i].sc;
        if(viz != p[s]){
            if(dist[viz]){
                if(dist[viz] < dist[s]){
                    back_edge temp; temp.d = dist[viz]; temp.v = viz; temp.id = id;
                    be[s].insert(temp);
                }
                continue;
            }

            p[viz] = s;
            dist[viz] = dist[s]+1;
            dfsIni(viz);
        }
    }
}

void imprime(int a, int b){
    while(a != b){
        cout<<a<<" ";
        a = p[a];
    }
    cout<<b<<" ";
}

void dfs(int s){
    marc[s] = 1;

    if(sz(be[s]) > 0){
        auto it = be[s].begin();
        vector< set<back_edge>::iterator > v;
        while(it != be[s].end() && sz(cur) > 0){
            int x = cur.back();
            if(it->v == x){
                v.push_back(it);
                imprime(s,x);
                cout<<"\n";
            }else{
                back_edge temp; temp.d = it->d; temp.v = 0; temp.id = 0;
                auto it2 = be[x].lower_bound(temp);
                if(it2 == be[x].end())break;
                imprime(s,x);
                imprime(it2->v,it->v);
                cout<<"\n";
                be[x].erase(it2);
                if(sz(be[x]) == 0)cur.pop_back();
                v.push_back(it);
            }
            it++;
        }

        for(auto it : v)be[s].erase(it);
    }

    if(sz(be[s]) > 0)cur.push_back(s);

    for(int i = 0; i < sz(adj[s]); i++){
        int viz = adj[s][i].fi, id = adj[s][i].sc;
        if(!marc[viz])dfs(viz);
    }

    if(sz(cur) > 0 && cur.back() == s){
        imprime(s,be[s].begin()->v);
        cout<<"\n";
        cur.pop_back();
    }

}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n,m; cin>>n>>m;
    for(int i = 1; i <= m; i++){
        int a,b; cin>>a>>b;
        adj[a].emplace_back(b,i);
        adj[b].emplace_back(a,i);
    }

    dist[1] = 1;
    dfsIni(1);

    dfs(1);
}

Compilation message (stderr)

postmen.cpp: In function 'void dfs(int)':
postmen.cpp:79:33: warning: unused variable 'id' [-Wunused-variable]
   79 |         int viz = adj[s][i].fi, id = adj[s][i].sc;
      |                                 ^~

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