oj.uz

Submission #42221

# Submission time Handle Problem Language Result Execution time Memory
42221 2018-02-23T18:30:10 Z gabrielsimoes Senior Postmen (BOI14_postmen) C++14
0 / 100
 500 ms 24320 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");
}

void print(vector<vector<int>>& v) {
  for (vector<int>& u : v) print(u, 0);
}

void copy(vector<int>& v, int pos, vector<vector<int>>& result) {
  result.push_back(vector<int>());
  while (pos < v.size()) result.back().push_back(v[pos++]);
}

vector<int> stk;
vector<int> in[MAXN];
vector<vector<int>> result;

vector<vector<int>> solve(int start, int n) {
  stk.clear();
  result.clear();
  for (int i = 1; i <= n; i++) in[i].clear();

  for (int i = start; i < v.size(); i++) {
    int x = v[i];
    // printf("%d ", x);
    if (!in[x].empty()) {
      int pos = in[x].back();
      copy(stk, pos, result);
      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);
  }
  // printf("\n");

  copy(stk, 0, result);
  return result;
}

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);

  // print(v, 0);

  vector<vector<int>> ans;
  int lim = v.size();
  for (int i = 0; i < lim; i++) {
    vector<vector<int>> result = solve(i, n);
    if (ans.empty() || ans.size() > result.size()) ans = result;
    v.push_back(v[i]);
    // printf("beginning at %d : %d\n", i, result.size());
  }

  print(ans);
}

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 'void copy(std::vector<int>&, int, std::vector<std::vector<int> >&)':
postmen.cpp:32:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (pos < v.size()) result.back().push_back(v[pos++]);
          ~~~~^~~~~~~~~~
postmen.cpp: In function 'std::vector<std::vector<int> > solve(int, int)':
postmen.cpp:44:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = start; i < v.size(); i++) {
                       ~~^~~~~~~~~~
postmen.cpp:50: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: In function 'int main()':
postmen.cpp:65: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:68: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 Correct 18 ms 23808 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 18 ms 23808 KB Output is correct
4 Execution timed out 708 ms 24320 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23800 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 21 ms 23820 KB Output is correct
4 Execution timed out 730 ms 24316 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23808 KB Output is correct
2 Correct 22 ms 23784 KB Output is correct
3 Correct 18 ms 23808 KB Output is correct
4 Execution timed out 697 ms 24288 KB Time limit exceeded
5 Halted 0 ms 0 KB -