Submission #1074984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074984		RauPro	Senior Postmen (BOI14_postmen)	C++17	38 / 100	1060 ms	32596 KiB

postmen

#include <bits/stdc++.h>
 
using namespace std;
 
typedef pair<int,int> ii;
typedef int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii; 
typedef vector<vii> wgraf;
typedef pair<int,ii> edge;
typedef vector <ll> vl;
typedef pair <ll, ll> LL;
typedef vector <LL> vll;
 
#define UNVISITED 0
#define VISITED 1
#define pb push_back
#define F first
#define S second
 
ll n, m, u, v, visto[500005], cone[500005];
vll grafo[500005];
bool vale = false, puede[500005];
map<int, int> conections;
 
void dfs(ll origen, ll nodo, ll padre, ll aux) {
  if (conections[nodo] == grafo[nodo].size()){
      return;
  }
  if (nodo == origen && padre != -1) {
    vale = true;
    return;
  }
  
  for (auto i : grafo[nodo]) {
 
    if (i.F != padre && puede[i.S] == true && visto[i.F] != aux) {
    
      puede[i.S] = false;
      visto[i.F] = aux;
      
      dfs(origen, i.F, nodo, aux);
      
      if (vale == true) {
        conections[nodo]++;
        cout << nodo << " ";
 
        return;
      
      }
      
      puede[i.S] = true;
    
    }
    
  }
 
}
 
void SOLVE(){
  cin >> n >> m;
 
  for (ll i = 0; i < n; i++) visto[i] = 0;
 
  for (ll i = 0; i < m; i++){
    cin >> u >> v;
 
    grafo[u].pb({v, i});
    grafo[v].pb({u, i});
 
    puede[i] = true;
    cone[i] = u;
  }
 
  ll cnt = 0;
 
  for (ll i = 0; i < m; i++) {
    if (puede[i] == true) {
      vale = false;
      cnt++;
      dfs(cone[i], cone[i], -1, cnt);
      cout << "\n";
    }
  }
}
 
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t = 1;
  //cin >> t;
  while(t--){
    SOLVE();
  }
}

Compilation message (stderr)

postmen.cpp: In function 'void dfs(ll, ll, ll, ll)':
postmen.cpp:28:24: warning: comparison of integer expressions of different signedness: 'std::map<int, int>::mapped_type' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   if (conections[nodo] == grafo[nodo].size()){

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