#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)
#define lb(x,y) lower_bound(all(x),y)-begin(x)
mt19937 rng;
class Hierholzer { public:
struct Edge { int to, rev; bool vis; };
vector<vector<Edge>> adj;
bool dir;
int N, M;
void addEdge(int u, int v) {
int pos1 = sz(adj[u]), pos2 = sz(adj[v]);
if (u == v) pos2++;
adj[u].pb({v, pos2, 0});
if (!dir) adj[v].pb({u, pos1, 0});
M++;
}
vector<int> adjPos;
void rec(vector<int> &res, int u) {
while (adjPos[u] < sz(adj[u]) && adj[u][adjPos[u]].vis) adjPos[u]++;
if (adjPos[u] < sz(adj[u])) {
Edge e = adj[u][adjPos[u]];
if (!dir) adj[e.to][e.rev].vis = true;
adj[u][adjPos[u]++].vis = true;
rec(res, e.to);
rec(res, u);
} else res.pb(u);
}
bool possible(int start, int end) {
if (dir) {
vector<int> inCnt(N, 0), outCnt(N, 0);
for (int u = 0; u < N; u++) outCnt[u] = sz(adj[u]);
for (int u = 0; u < N; u++) for (Edge e : adj[u]) inCnt[e.to]++;
if (start == end && inCnt[start] != outCnt[start]) return false;
if (start != end && inCnt[start] + 1 != outCnt[start]) return false;
if (start != end && inCnt[end] != outCnt[end] + 1) return false;
for (int i = 0; i < sz(adj); i++)
if (i != start && i != end && inCnt[i] != outCnt[i]) return false;
} else {
if (start == end && sz(adj[start]) % 2 == 1) return false;
if (start != end && (sz(adj[start]) + sz(adj[end])) % 2 == 1) return false;
for (int i = 0; i < sz(adj); i++)
if (i != start && i != end && sz(adj[i]) % 2 == 1) return false;
}
return true;
}
bool path(vector<int> &res, int start, int end) {
if (!possible(start, end)) return false;
adjPos = vector<int>(sz(adj), 0);
rec(res, start);
reverse(res.begin(), res.end());
return sz(res) == M + 1;
}
Hierholzer(int _N, bool directed) {
N = _N; M = 0;
adj = vector<vector<Edge>>(N);
dir = directed;
}
};
void solve() {
int N, M; cin >> N >> M;
Hierholzer h(N, false);
for (int i = 0; i < M; i++) {
int u, v; cin >> u >> v; u--; v--;
h.addEdge(u, v);
}
vector<int> path;
h.path(path, 0, 0);
vector<int> prev(N, -1);
vector<int> nxt, pos;
stack<int> st;
for (int i = 0; i < sz(path); i++) {
if (prev[path[i]] >= 0) {
vector<int> curPath;
int j = pos[prev[path[i]]];
while (!st.empty() && st.top() >= j) {
curPath.pb(path[st.top()]);
prev[path[st.top()]] = nxt[prev[path[st.top()]]];
st.pop();
}
for (int i = 0; i < sz(curPath); i++) {
cout << (curPath[i] + 1) << (i == sz(curPath) - 1 ? "\n" : " ");
}
}
pos.pb(i);
nxt.pb(prev[path[i]]);
prev[path[i]] = sz(nxt) - 1;
st.push(i);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());
solve();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
320 KB |
Output is correct |
4 |
Correct |
2 ms |
588 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
724 KB |
Output is correct |
7 |
Correct |
4 ms |
1764 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
24 ms |
7876 KB |
Output is correct |
10 |
Correct |
1 ms |
596 KB |
Output is correct |
11 |
Correct |
1 ms |
596 KB |
Output is correct |
12 |
Correct |
26 ms |
8292 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
724 KB |
Output is correct |
7 |
Correct |
6 ms |
1744 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
24 ms |
7908 KB |
Output is correct |
10 |
Correct |
1 ms |
596 KB |
Output is correct |
11 |
Correct |
1 ms |
596 KB |
Output is correct |
12 |
Correct |
28 ms |
8340 KB |
Output is correct |
13 |
Correct |
38 ms |
11908 KB |
Output is correct |
14 |
Correct |
40 ms |
10212 KB |
Output is correct |
15 |
Correct |
39 ms |
10364 KB |
Output is correct |
16 |
Correct |
36 ms |
11860 KB |
Output is correct |
17 |
Correct |
40 ms |
8436 KB |
Output is correct |
18 |
Correct |
38 ms |
10256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
724 KB |
Output is correct |
7 |
Correct |
4 ms |
1772 KB |
Output is correct |
8 |
Correct |
2 ms |
468 KB |
Output is correct |
9 |
Correct |
27 ms |
7904 KB |
Output is correct |
10 |
Correct |
2 ms |
568 KB |
Output is correct |
11 |
Correct |
1 ms |
596 KB |
Output is correct |
12 |
Correct |
26 ms |
8356 KB |
Output is correct |
13 |
Correct |
36 ms |
11944 KB |
Output is correct |
14 |
Correct |
36 ms |
10316 KB |
Output is correct |
15 |
Correct |
45 ms |
10472 KB |
Output is correct |
16 |
Correct |
36 ms |
11888 KB |
Output is correct |
17 |
Correct |
39 ms |
8328 KB |
Output is correct |
18 |
Correct |
44 ms |
10308 KB |
Output is correct |
19 |
Correct |
337 ms |
63368 KB |
Output is correct |
20 |
Correct |
327 ms |
53160 KB |
Output is correct |
21 |
Correct |
281 ms |
53796 KB |
Output is correct |
22 |
Correct |
339 ms |
63508 KB |
Output is correct |
23 |
Correct |
131 ms |
36944 KB |
Output is correct |
24 |
Correct |
310 ms |
44728 KB |
Output is correct |
25 |
Correct |
302 ms |
54440 KB |
Output is correct |