Submission #62882

#	Time	Username	Problem	Language	Result	Execution time	Memory
62882		IvanC	Senior Postmen (BOI14_postmen)	C++17	55 / 100	534 ms	76756 KiB

postmen

#include <bits/stdc++.h>
#define gc getchar_unlocked
inline void getint(int &x){
    register int c = gc();
    x = 0;
    for(;(c<48 || c>57);c = gc());
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
}
inline void print(int n){
    char buf[11];
    buf[10] = ' ';
    int i = 9;
    while (n)
    {
      buf[i--] = n % 10 + '0';
      n /= 10;
    }
    while (buf[i] != ' ')
      putchar_unlocked(buf[++i]);
}
using namespace std;
typedef vector<int> vi;
const int MAXN = 5*1e5 + 10;
int N,M,e1[MAXN],e2[MAXN],e3[MAXN],marcado[MAXN],ptr[MAXN];
vi grafo[MAXN],pilha;
vector<vi> resposta;
int dfs(int v){
  //printf("DFS %d\n",v);
  marcado[v] = 1;
  for(;ptr[v] < grafo[v].size();ptr[v]++){
    int idx = grafo[v][ptr[v]];
    if(e3[idx] == 1) continue;
    e3[idx] = 1;
    int u = (e1[idx] != v) ? (e1[idx]) : (e2[idx]);
    if(marcado[u]){
      marcado[v] = 0;
      pilha.push_back(v);
      return u;
    }
    int ret = dfs(u);
    if(ret == v){
      pilha.push_back(v);
      resposta.push_back(pilha);
      pilha.clear();
    }
    else{
      marcado[v] = 0;
      pilha.push_back(v);
      return ret;
    }
  }
  marcado[v] = 0;
  pilha.clear();
  return -1;
}
int main(){
  scanf("%d %d",&N,&M);
  for(int i = 1;i<=M;i++){
    getint(e1[i]);
    getint(e2[i]);
    grafo[e1[i]].push_back(i);
    grafo[e2[i]].push_back(i);
  }
  for(int i = 1;i<=N;i++){
    dfs(i);
  }
  for(int i = 0;i<resposta.size();i++){
    for(int j : resposta[i]) print(j);
    printf("\n");
  }
  return 0;
}

Compilation message (stderr)

postmen.cpp: In function 'void getint(int&)':
postmen.cpp:4:18: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
     register int c = gc();
                  ^
postmen.cpp: In function 'int dfs(int)':
postmen.cpp:30:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(;ptr[v] < grafo[v].size();ptr[v]++){
        ~~~~~~~^~~~~~~~~~~~~~~~~
postmen.cpp: In function 'int main()':
postmen.cpp:67:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0;i<resposta.size();i++){
                 ~^~~~~~~~~~~~~~~~
postmen.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&N,&M);
   ~~~~~^~~~~~~~~~~~~~~

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