oj.uz

답안 #656492

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
656492 2022-11-07T15:40:53 Z 600Mihnea 어르신 집배원 (BOI14_postmen) C++17
100 / 100
 405 ms 75488 KB 
bool home = 0;
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 500000 + 7;
int n;
int m;
int sum[N];
bool vis[N];
vector<int> g[N];
vector<int> ord;

void go(int a) {
  while (!g[a].empty()) {
    int i = g[a].back();
    g[a].pop_back();
    if (vis[i]) {
      continue;
    }
    vis[i] = 1;
    go(sum[i] - a);
    ord.push_back(a);
  }
}

signed main() {
  if (home == 0) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  } else {
    freopen ("___input___.txt", "r", stdin);
  }

  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    sum[i] = a + b;
    g[a].push_back(i);
    g[b].push_back(i);
  }
  go(1);
  for (int i = 1; i <= m; i++) {
    assert(vis[i]);
  }
  for (int i = 1; i <= n; i++) {
    vis[i] = 0;
  }
  assert((int) ord.size() == m);
  assert(!ord.empty());
  ord.push_back(ord[0]);

  vector<int> stk;
  for (auto &x : ord) {
    if (vis[x] == 0) {
      stk.push_back(x);
      vis[x] = 1;
      continue;
    }
    cout << x << " ";
    while (stk.back() != x) {
      cout << stk.back() << " ";
      vis[stk.back()] = 0;
      stk.pop_back();
    }
    cout << "\n";
  }
  return 0;
  while ((int) ord.size() > 1) {
    int dim = (int) ord.size();
    set<int> s;
    for (int r = 0; r < dim; r++) {
      int x = ord[r];
      if (s.count(x)) {
        s.clear();
        int l = r;
        s.insert(ord[l]);
        while (!s.count(ord[l - 1])) {
          l--;
          s.insert(ord[l]);
        }
        vector<int> new_ord, now;
        for (int j = 0; j < dim; j++) {
          if (l <= j && j <= r) {
            now.push_back(ord[j]);
            continue;
          }
          new_ord.push_back(ord[j]);
        }
        for (auto &v : now) {
          cout << v << " ";
        }
        cout << "\n";
        ord = new_ord;
        break;
      } else {
        s.insert(x);
      }
    }
  }
  if (0) {
    cout << " ---> ";
    for (auto &x : ord) {
      cout << x << " ";
    }
    cout << "\n";
  }

  return 0;
}

Compilation message

postmen.cpp: In function 'int main()':
postmen.cpp:33:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     freopen ("___input___.txt", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 7 ms 12372 KB Output is correct
5 Correct 7 ms 12156 KB Output is correct
6 Correct 9 ms 12492 KB Output is correct
7 Correct 11 ms 13396 KB Output is correct
8 Correct 7 ms 12244 KB Output is correct
9 Correct 36 ms 20644 KB Output is correct
10 Correct 7 ms 12244 KB Output is correct
11 Correct 7 ms 12212 KB Output is correct
12 Correct 39 ms 21700 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 6 ms 12052 KB Output is correct
4 Correct 8 ms 12300 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 7 ms 12500 KB Output is correct
7 Correct 11 ms 13396 KB Output is correct
8 Correct 7 ms 12244 KB Output is correct
9 Correct 36 ms 20632 KB Output is correct
10 Correct 8 ms 12212 KB Output is correct
11 Correct 7 ms 12244 KB Output is correct
12 Correct 38 ms 21788 KB Output is correct
13 Correct 55 ms 24576 KB Output is correct
14 Correct 53 ms 20528 KB Output is correct
15 Correct 56 ms 23072 KB Output is correct
16 Correct 59 ms 24532 KB Output is correct
17 Correct 51 ms 17568 KB Output is correct
18 Correct 53 ms 21940 KB Output is correct

Subtask #3
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 7 ms 12372 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 8 ms 12500 KB Output is correct
7 Correct 12 ms 13404 KB Output is correct
8 Correct 7 ms 12300 KB Output is correct
9 Correct 34 ms 20676 KB Output is correct
10 Correct 8 ms 12216 KB Output is correct
11 Correct 8 ms 12228 KB Output is correct
12 Correct 40 ms 21740 KB Output is correct
13 Correct 56 ms 24516 KB Output is correct
14 Correct 51 ms 20548 KB Output is correct
15 Correct 50 ms 22964 KB Output is correct
16 Correct 64 ms 24516 KB Output is correct
17 Correct 55 ms 17496 KB Output is correct
18 Correct 58 ms 21940 KB Output is correct
19 Correct 395 ms 75488 KB Output is correct
20 Correct 385 ms 55872 KB Output is correct
21 Correct 340 ms 67440 KB Output is correct
22 Correct 405 ms 75472 KB Output is correct
23 Correct 157 ms 58020 KB Output is correct
24 Correct 400 ms 40524 KB Output is correct
25 Correct 390 ms 62456 KB Output is correct