oj.uz

Submission #42216

# Submission time Handle Problem Language Result Execution time Memory
42216 2018-02-23T17:48:17 Z gabrielsimoes Senior Postmen (BOI14_postmen) C++14
0 / 100
 21 ms 23860 KB 
#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());

  print(v, 0);

  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

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:48: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
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 23808 KB Edge does not exist or used 1, 3
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 23808 KB Edge does not exist or used 1, 3
2 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 23860 KB Edge does not exist or used 1, 3
2 Halted 0 ms 0 KB -