Submission #960674

#	Time	Username	Problem	Language	Result	Execution time	Memory
960674		dpsaveslives	Senior Postmen (BOI14_postmen)	C++17	100 / 100	328 ms	71364 KiB

postmen

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int MAXN = 5e5+10;
vector<pair<int,int>> adj[MAXN]; //for knowing whether we visited this edge before, we save the edge index
vector<bool> visedge, vis;
vector<int> cyc;
int cur;
void dfs(int u){
    vis[u] = true; cyc.push_back(u);
    while(!adj[u].empty()){
        while(!adj[u].empty() && visedge[adj[u].back().s]){
            adj[u].pop_back();
        }
        if(adj[u].empty()){ //give up -> this one won't be added in the cycle!
            cyc.pop_back();
            return;
        }
        int v = adj[u].back().f;
        visedge[adj[u].back().s] = true;
        if(vis[v]){
            cur = v;
            cout << v << " ";
            while(cyc.back() != v){
                cout << cyc.back() << " ";
                vis[cyc.back()] = false; cyc.pop_back();
            }
            cout << "\n";
        }
        else{
            dfs(v);
        }
        if(u != cur){
            //AHHHHHH (we cannot continue here)
            return;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N,M; cin >> N >> M;
    visedge = vector<bool>(M,false), vis = vector<bool>(N+1,false);
    for(int i = 0;i<M;++i){
        int u,v; cin >> u >> v;
        adj[u].push_back({v,i}); adj[v].push_back({u,i});
    }
    for(int i = 1;i<=N;++i){ //is this necessary? Or can we just do it in one? It is necessary! Otherwise we might get stuck
        dfs(i);
    }
    return 0;
}

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