답안 #894851

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
894851	2023-12-29T06:01:16 Z	qrno	어르신 집배원 (BOI14_postmen)	C++17	100 / 100	459 ms	69552 KB

postmen

/*
Solution Plan:
  Maybe just find an eulerian cycle then
  go through the cycle, if you find a vertex that was
  visited before, form a cycle with the vertices going back
  to the last appearence of the vertex
*/

#include <bits/stdc++.h>
using namespace std;

int N, M;
vector<vector<pair<int, int>>> G;
vector<bool> used;

vector<int> path;
void dfs(int v) {
  while (!G[v].empty()) {
    auto [u, id] = G[v].back();
    G[v].pop_back();
    if (used[id]) continue;
    used[id] = true;
    dfs(u);
  }
  path.push_back(v);
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> N >> M;
  G.resize(N);
  used.assign(M, false);
  for (int i = 0; i < M; i++) {
    int v, u;
    cin >> v >> u;
    v--, u--;
    G[v].push_back({u, i});
    G[u].push_back({v, i});
  }
  dfs(0);

  /* cout << "path: "; */
  /* for (auto v : path) cout << v+1 << " "; */
  /* cout << endl; */

  stack<int> S;
  vector<vector<int>> ans;

  vector<bool> seen(N);
  for (auto v : path) {
    if (seen[v]) {
      vector<int> tour;
      while (seen[v]) {
        int u = S.top();
        S.pop();
        seen[u] = false;
        tour.push_back(u);
      }
      ans.push_back(tour);
    }
    S.push(v);
    seen[v] = true;
  }

  for (auto tour : ans) {
    for (auto v : tour) cout << v+1 << ' ';
    cout << endl;
  }
}

Subtask #1

38.0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	504 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	3 ms	604 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	2 ms	720 KB	Output is correct
7	Correct	5 ms	1884 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	28 ms	8984 KB	Output is correct
10	Correct	3 ms	600 KB	Output is correct
11	Correct	2 ms	768 KB	Output is correct
12	Correct	32 ms	9516 KB	Output is correct

Subtask #2

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	3 ms	604 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	2 ms	860 KB	Output is correct
7	Correct	7 ms	1876 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	28 ms	8916 KB	Output is correct
10	Correct	2 ms	600 KB	Output is correct
11	Correct	2 ms	768 KB	Output is correct
12	Correct	32 ms	9532 KB	Output is correct
13	Correct	34 ms	13764 KB	Output is correct
14	Correct	62 ms	10620 KB	Output is correct
15	Correct	82 ms	13000 KB	Output is correct
16	Correct	34 ms	13776 KB	Output is correct
17	Correct	74 ms	9032 KB	Output is correct
18	Correct	64 ms	12256 KB	Output is correct

Subtask #3

45.0 / 45.0

#	결과	실행 시간	메모리	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	Correct	2 ms	604 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	3 ms	860 KB	Output is correct
7	Correct	5 ms	1880 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	31 ms	8916 KB	Output is correct
10	Correct	2 ms	604 KB	Output is correct
11	Correct	2 ms	604 KB	Output is correct
12	Correct	35 ms	9592 KB	Output is correct
13	Correct	36 ms	13768 KB	Output is correct
14	Correct	71 ms	10824 KB	Output is correct
15	Correct	71 ms	12996 KB	Output is correct
16	Correct	36 ms	13768 KB	Output is correct
17	Correct	73 ms	9300 KB	Output is correct
18	Correct	76 ms	12468 KB	Output is correct
19	Correct	309 ms	69552 KB	Output is correct
20	Correct	449 ms	53700 KB	Output is correct
21	Correct	459 ms	65068 KB	Output is correct
22	Correct	290 ms	69288 KB	Output is correct
23	Correct	156 ms	42136 KB	Output is correct
24	Correct	455 ms	46008 KB	Output is correct
25	Correct	402 ms	60796 KB	Output is correct