oj.uz

Submission #42218

# Submission time Handle Problem Language Result Execution time Memory
42218 2018-02-23T17:50:41 Z gabrielsimoes Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 80584 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());

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

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23804 KB Output is correct
2 Correct 24 ms 23808 KB Output is correct
3 Correct 20 ms 23808 KB Output is correct
4 Correct 20 ms 24064 KB Output is correct
5 Correct 22 ms 23936 KB Output is correct
6 Correct 21 ms 24192 KB Output is correct
7 Correct 25 ms 25024 KB Output is correct
8 Correct 22 ms 24040 KB Output is correct
9 Correct 67 ms 29936 KB Output is correct
10 Correct 21 ms 24064 KB Output is correct
11 Correct 18 ms 24064 KB Output is correct
12 Correct 73 ms 30228 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 20 ms 23808 KB Output is correct
3 Correct 18 ms 23808 KB Output is correct
4 Correct 18 ms 24064 KB Output is correct
5 Correct 19 ms 23988 KB Output is correct
6 Correct 20 ms 24192 KB Output is correct
7 Correct 30 ms 24960 KB Output is correct
8 Correct 24 ms 24064 KB Output is correct
9 Correct 62 ms 29820 KB Output is correct
10 Correct 20 ms 24064 KB Output is correct
11 Correct 24 ms 24192 KB Output is correct
12 Correct 66 ms 30204 KB Output is correct
13 Correct 110 ms 35188 KB Output is correct
14 Correct 102 ms 32068 KB Output is correct
15 Correct 107 ms 32876 KB Output is correct
16 Correct 116 ms 35188 KB Output is correct
17 Correct 108 ms 30392 KB Output is correct
18 Correct 147 ms 32772 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 22 ms 23808 KB Output is correct
3 Correct 22 ms 23808 KB Output is correct
4 Correct 25 ms 24192 KB Output is correct
5 Correct 18 ms 23912 KB Output is correct
6 Correct 26 ms 24192 KB Output is correct
7 Correct 26 ms 24960 KB Output is correct
8 Correct 21 ms 24064 KB Output is correct
9 Correct 62 ms 29824 KB Output is correct
10 Correct 23 ms 24064 KB Output is correct
11 Correct 25 ms 24064 KB Output is correct
12 Correct 67 ms 30308 KB Output is correct
13 Correct 113 ms 35060 KB Output is correct
14 Correct 106 ms 32108 KB Output is correct
15 Correct 91 ms 32916 KB Output is correct
16 Correct 120 ms 35036 KB Output is correct
17 Correct 118 ms 30332 KB Output is correct
18 Correct 107 ms 32732 KB Output is correct
19 Execution timed out 588 ms 80584 KB Time limit exceeded
20 Halted 0 ms 0 KB -