# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
896146 | 2023-12-31T22:17:59 Z | damamila | 어르신 집배원 (BOI14_postmen) | C++14 | 1 ms | 348 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>> g(n); for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; a--; b--; g[a].insert(b); g[b].insert(a); } //dont need to check if possible bc question says is possible vector<int> seq; stack<int> stak; stak.push(0); 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 map<int, int> index; vector<pair<int, int>> groups; //end then start, should have soonest end points first for (int i = 0; i < seq.size(); i++) { int a = seq[i]; if (index[a] != 0) { //used before groups.push_back({i+1, index[a]}); index[a] = 0; } else { index[a] = i+1; //so no confusion if in first position } } int lb = n; //leftmost which has been done int rb = 0; //rightmost which has been done for (auto x : groups) { if (x.second < lb || x.second > rb) { //if no overlap with prev for (int i = x.second-1; i < x.first-1; i++) { if (i < lb || i >= rb) { cout << seq[i]+1 << " "; } } cout << endl; lb = x.second-1; rb = x.first-1; } } } //TL really soon
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Incorrect | 0 ms | 348 KB | Same junction appears twice in a route |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Incorrect | 1 ms | 348 KB | Same junction appears twice in a route |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Incorrect | 0 ms | 344 KB | Same junction appears twice in a route |
3 | Halted | 0 ms | 0 KB | - |