Submission #1047141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047141		TraianDanciu	Senior Postmen (BOI14_postmen)	C++17	100 / 100	200 ms	44116 KiB

postmen

#include <stdio.h>
#include <vector>

#define MAXN 500000

struct Edge {
  int v, idx;
};
std::vector<Edge> g[MAXN];
int stiva[MAXN + 1], ans[MAXN + 1], rez[MAXN + 1];
char viz[MAXN];

int main() {
  int n, m, i, u, v, sp, nciclu, ptr;
  
  scanf("%d%d", &n, &m);
  for(i = 0; i < m; i++) {
    scanf("%d%d", &u, &v);
    g[--u].push_back((struct Edge){.v = --v, .idx = i});
    g[v].push_back((struct Edge){.v = u, .idx = i});
  }
  
  sp = 1;
  nciclu = 0;
  while(sp > 0) {
    u = stiva[sp - 1];
    if(g[u].empty()) {
      ans[nciclu++] = u;
      sp--;
    } else {
      v = g[u].back().v;
      i = g[u].back().idx;
      g[u].pop_back();
      if(viz[i] == 0) {
        viz[i] = 1;
        stiva[sp++] = v;
      }
    }
  }
  
  for(i = 0; i < n; i++) {
    viz[i] = 0;
  }
  ptr = 0;
  
  for(i = nciclu - 1; i >= 0; i--) {
    if(viz[ans[i]]) {
      printf("%d ", ans[i] + 1);
      while(rez[ptr - 1] != ans[i]) {
        viz[rez[--ptr]] = 0;
        printf("%d ", rez[ptr] + 1);
      }
      fputc('\n', stdout);
    } else {
      viz[rez[ptr++] = ans[i]] = 1;
    }
  }
  
  return 0;
}

Compilation message (stderr)

postmen.cpp: In function 'int main()':
postmen.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
postmen.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf("%d%d", &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~

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