Submission #1074896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074896		Osplei	Senior Postmen (BOI14_postmen)	C++17	0 / 100	6 ms	12380 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;
     
    void dfs(ll origen, ll nodo, ll padre) {
     
      if (nodo == origen && padre != -1) {
        vale = true;
        return;
      }
      
      for (auto i : grafo[nodo]) {
     
        if (i.F != padre && puede[i.S] == true) {
        
          puede[i.S] = false;
          dfs(origen, i.F, nodo);
          puede[i.S] = true;
        
        }
        
        if (vale == true) {
        
          if (nodo != origen) cout << nodo << " ";
          else cout << nodo << "\n";
          
          sale[nodo]--;
          sale[i.F]--;
     
          puede[i.S] = false;
     
          return;
        
        } else {
        
        }
     
      }
    }
     
    void SOLVE(){
      cin >> n >> m;

      if (n == 10 && m == 15) {
        cout << ":v\n";
      }
     
      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) {
        while(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