Submission #1050278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050278		kebine	Senior Postmen (BOI14_postmen)	C++17	100 / 100	225 ms	65056 KiB

postmen

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
vector<pair<int, int>> adj[500005];
int ind[500005];
bool ya[500005], vis[500005];
vector<pair<int, int>> star;

void dfs(int a) {
  stack<int> s;
  s.push(a);
  vis[a] = true;
  while(true) {
    int b = s.top();
    while(true) {
      if(ind[b] == adj[b].size()) {
        break;
      }
      int c = adj[b][ind[b]].second;
      if(ya[c] == true) {
        ind[b]++;
      } else {
        break;
      }
    }
    if(ind[b] == adj[b].size()) {
      //cout << b << "\n";
      if(s.size() > 1) {
        while(!s.empty()) {
          cout << s.top() << " ";
          vis[s.top()] = false;
          s.pop();
        }
        cout << "\n";
      } else {
        vis[b] = false;
      }
      
      break;
    }
    
    int nxt = adj[b][ind[b]].first, jo = adj[b][ind[b]].second;
    ind[b]++;
    ya[jo] = true;
    if(vis[nxt] == true) {
      cout << nxt << " ";
      while(s.top() != nxt) {
        cout << s.top() << " ";
        vis[s.top()] = false;
        s.pop();
      }
      cout << "\n";
    } else {
      vis[nxt] = true;
      s.push(nxt);
    }
    
  }
}

signed main() {
  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin >> n >> m;
  for(int i = 0; i < m; i++) {
    int y, z;
    cin >> y >> z;
    star.push_back({y, z});
    adj[y].push_back({z, i});
    adj[z].push_back({y, i});
  }
  for(int i = 0; i < m; i++) {
    if(ya[i] == false) {
      ya[i] = true;
      //cout << i << "\n";
      dfs(star[i].first);
    }
  }
  
}

Compilation message (stderr)

postmen.cpp: In function 'void dfs(long long int)':
postmen.cpp:17:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |       if(ind[b] == adj[b].size()) {
      |          ~~~~~~~^~~~~~~~~~~~~~~~
postmen.cpp:27:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     if(ind[b] == adj[b].size()) {
      |        ~~~~~~~^~~~~~~~~~~~~~~~

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