제출 #1074936

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1074936		RauPro	어르신 집배원 (BOI14_postmen)	C++17	0 / 100	1041 ms	13152 KiB

postmen

#include <bits/stdc++.h>
 
using namespace std;
 
typedef pair<int,int> ii;
typedef long long 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;
vll grafo[500005];
map <ll, ll> sale;
map <ll, bool> puede;
bool visto[500005], vale = false;
map <ll, bool> arista;


void dfs(ll origen, ll nodo, ll padre) {
 
  if (nodo == origen && padre != -1) {
    vale = true;
    return;
  }
  
  for (auto i : grafo[nodo]) {
    if (arista[i.S]){
        continue;
    }
    if (i.F != padre && puede[i.S] == true && visto[i.F] == false) {
    
      puede[i.S] = false;
      visto[i.F] = true;
      
      dfs(origen, i.F, nodo);
      
      puede[i.S] = true;
      visto[i.F] = false;
    
    }
    
    if (vale == true) {
    
      if (nodo != origen) cout << nodo << " ";
      else cout << nodo << "\n";
      arista[i.S] = 1;
      sale[nodo]--;
      sale[i.F]--;
 
      puede[i.S] = false;
 
      return;
    
    }
 
  }
}
 
/*
4 10
1 2
2 3
3 4
4 1
5 6
6 7
7 8
8 5
2 5
8 3
*/
 
void SOLVE(){
  cin >> n >> m;
 
  for (ll i = 0; i < n; i++) visto[i] = false;
 
  for (ll i = 0; i < m; i++){
    cin >> u >> v;
 
    grafo[u].pb({v, i});
    grafo[v].pb({u, i});
 
    sale[u]++;
    sale[v]++;
 
    puede[i] = true;
  }
 
  for (auto i : sale) {
    if(i.S > 0) {
      vale = false;
      dfs(i.F, i.F, -1);
      i.S--;
    }
  }
}
 
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t = 1;
  //cin >> t;
  while(t--){
    SOLVE();
  }
}

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