# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
896114 | 2023-12-31T20:15:02 Z | damamila | 어르신 집배원 (BOI14_postmen) | C++14 | 4 ms | 1124 KB |
#include <bits/stdc++.h> using namespace std; #define int long long signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector<set<int>> graph(n); for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; a--; b--; graph[a].insert(b); graph[b].insert(a); } //dont need to check if possible bc question says is possible for (int i = 0; i < n; i++) { //for every vertex while (graph[i].size() > 0) { //whilst tours can start from here vector<set<int>> g = graph; //so not remove all edges forever vector<int> seq; stack<int> stak; stak.push(i); while (!stak.empty()) { int u = stak.top(); //~ cout << u+1 << endl; if (g[u].size() > 0) { //if still neighbours int v = *g[u].begin(); stak.push(v); g[u].erase(v); //erase edge from both sides g[v].erase(u); } else { //need to add to tour stak.pop(); seq.push_back(u); //~ cout << u+1 << " "; } } //~ cout << "seq " ; //~ for (int i : seq) { //~ cout << i+1 << " "; //~ } //~ cout << endl; //now make sure no vertices visited multiple times auto it = seq.begin()+1; vector<int> ans; ans.push_back(seq[0]); while (it < seq.end()) { //~ cout << *it+1; ans.push_back(*it); auto next = find(it+1, seq.end(), *it); if (next < seq.end()) { //if this knot occurs again it = next; //~ cout << " " << *it+1; } //~ cout << endl; it++; } int prev = -1; //~ cout << endl; for (int x : ans) { if (prev != -1) { //removal of edges used graph[prev].erase(x); graph[x].erase(prev); } prev = x; } for (int x = 1; x < ans.size(); x++) { cout << ans[x]+1 << " "; } cout << endl; } } } //ES GIBT KEINE MOEGLICHEN EULER TOUREN< WARUMMMMMMM
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Incorrect | 3 ms | 1116 KB | Same junction appears twice in a route |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Incorrect | 4 ms | 1112 KB | Same junction appears twice in a route |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Incorrect | 3 ms | 1124 KB | Same junction appears twice in a route |
5 | Halted | 0 ms | 0 KB | - |