Submission #42217

#	Time	Username	Problem	Language	Result	Execution time	Memory
42217		gabrielsimoes	Senior Postmen (BOI14_postmen)	C++14	55 / 100	567 ms	80716 KiB

postmen

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

const int MAXN = 500010;
vector<pair<int, int>> g[MAXN];
int ix[MAXN];
bool used[MAXN];

vector<int> v;
int dfs(int cur) {
  while (ix[cur] < g[cur].size()) {
    if (!used[g[cur][ix[cur]].second]) {
      used[g[cur][ix[cur]].second] = true;
      dfs(g[cur][ix[cur]].first);
      v.push_back(cur);
    }
    ix[cur]++;
  }
}

void print(vector<int>& v, int pos) {
  while (pos < v.size()) printf("%d ", v[pos++]);
  printf("\n");
}

vector<int> in[MAXN];

int main() {
  int n, m;
  scanf("%d %d", &n, &m);

  for (int i = 0, a, b; i < m; i++) {
    scanf("%d %d", &a, &b);
    g[a].push_back({b, i});
    g[b].push_back({a, i});
  }

  dfs(1);
  reverse(v.begin(), v.end());

  vector<int> stk;
  for (int x : v) {
    if (!in[x].empty()) {
      int pos = in[x].back();
      print(stk, pos);
      for (int i = pos; i < stk.size(); i++) in[stk[i]].pop_back();
      stk.resize(pos);
    }

    in[x].push_back(stk.size());
    stk.push_back(x);
  }

  print(stk, 0);
}

Compilation message (stderr)

postmen.cpp: In function 'int dfs(int)':
postmen.cpp:11:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (ix[cur] < g[cur].size()) {
          ~~~~~~~~^~~~~~~~~~~~~~~
postmen.cpp:19:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
postmen.cpp: In function 'void print(std::vector<int>&, int)':
postmen.cpp:22:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (pos < v.size()) printf("%d ", v[pos++]);
          ~~~~^~~~~~~~~~
postmen.cpp: In function 'int main()':
postmen.cpp:46:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = pos; i < stk.size(); i++) in[stk[i]].pop_back();
                         ~~^~~~~~~~~~~~
postmen.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~~
postmen.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &a, &b);
     ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 0 / 45