제출 #832693

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
832693		serifefedartar	Senior Postmen (BOI14_postmen)	C++17	55 / 100	559 ms	86708 KiB

postmen

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 20
#define MAXN 300005

vector<vector<pair<int,int>>> graph;
vector<pair<int,int>> edges;
vector<vector<int>> ans;
vector<int> pathVis;
bool active(int i) {
	if (edges[i].f == -1)
		return false;
	return true;
}

void deactivate(int i) {
	edges[i].f = edges[i].s = -1;
}

int go_back = 0;
void dfs(int node, int parent) {
	pathVis[node] = true;
	for (auto u : graph[node]) {
		if (u.f == parent || !active(u.s))
			continue;

		if (pathVis[u.f]) {
			ans.emplace_back();
			ans.back().push_back(u.f);
			go_back = u.f;
			deactivate(u.s);
			pathVis[node] = false;
		} else
			dfs(u.f, node);

		if (go_back) {
			if (go_back == node) {
				go_back = 0;
				deactivate(u.s);
				continue ;
			}
			ans.back().push_back(node);
			deactivate(u.s);
			pathVis[node] = false;
			return ;
		}
	}
	pathVis[node] = false;
}

int main() {
    fast
    int N, M, a, b;
    cin >> N >> M;

    graph = vector<vector<pair<int,int>>>(N+1, vector<pair<int,int>>());
    pathVis = vector<int>(N+1, false);
    for (int i = 0; i < M; i++) {
    	cin >> a >> b;
    	edges.push_back({a, b});
    	graph[a].push_back({b, edges.size()-1});
    	graph[b].push_back({a, edges.size()-1});
    }

    for (int i = 1; i <= N; i++)
    	dfs(i, i);

    for (auto u : ans) {
    	for (auto v : u)
    		cout << v << " ";
    	cout << "\n";
    }
}

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