Submission #462611

#	Time	Username	Problem	Language	Result	Execution time	Memory
462611		JovanB	Senior Postmen (BOI14_postmen)	C++17	55 / 100	543 ms	44728 KiB

postmen

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
vector <pair <int, int>> graf[500005];
 
bool visited[500005];
bool used[500005];
vector <vector <int>> cycles;
 
bool novi;
 
void ocisti(vector <pair <int, int>> &vec){
    while(!vec.empty() && used[vec.back().second]){
        vec.pop_back();
    }
}
 
void dfs(int tr){
    stack <int> stek;
    stek.push(tr);
    visited[tr] = 1;
    while(!stek.empty()){
        int v = stek.top();
        ocisti(graf[v]);
        if(novi){
            cycles.back().push_back(v);
            if(cycles.back()[0] == cycles.back()[cycles.back().size()-1]){
                novi = 0;
                continue;
            }
            stek.pop();
            visited[v] = 0;
            continue;
        }
        if(graf[v].empty()){
            visited[v] = 0;
            stek.pop();
            continue;
        }
        int c = graf[v].back().first;
        int g = graf[v].back().second;
        graf[v].pop_back();
        used[g] = 1;
        if(visited[c]){
            cycles.push_back({});
            cycles.back().push_back(c);
            novi = 1;
            continue;
        }
        else{
            stek.push(c);
            visited[c] = 1;
            continue;
        }
        stek.pop();
        visited[v] = 0;
    }
}
 
int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;
 
	int n, m;
	cin >> n >> m;
	int cnt = 0;
	for(int i=1; i<=m; i++){
        int a, b;
        cin >> a >> b;
        graf[a].push_back({b, ++cnt});
        graf[b].push_back({a, cnt});
	}
	int tr = 1;
	dfs(tr);
	while(tr <= n){
        dfs(tr);
        if(!graf[tr].size()) tr++;
	}
	for(auto cycle : cycles){
        cycle.pop_back();
        for(auto c : cycle) cout << c << " ";
        cout << "\n";
	}
    return 0;
}

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