oj.uz

Submission #1094895

# Submission time Handle Problem Language Result Execution time Memory
1094895 2024-09-30T19:23:12 Z andrewp Senior Postmen (BOI14_postmen) C++14
0 / 100
 0 ms 348 KB 
//Dedicated to my love, ivaziva
#pragma GCC optimize("Ofast") 
#include <bits/stdc++.h> 
using namespace std;  
 
using pii = pair<int, int>;
using ll = int64_t; 
 
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define dbg(x) cerr << #x << ": " << x << '\n';   

const int maxn = 5e5;    

int32_t main()  {
    ios::sync_with_stdio(false); cin.tie(nullptr);  
    cout.tie(nullptr); cerr.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> u(m), v(m);
    vector<bool> removed(m), was(n);
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        cin >> u[i] >> v[i], --u[i], --v[i];
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    vector<int> p(n);
    stack<int> stk;
    function<void(int)> dfs = [&](int x) {
        if (was[x]) {
            while (!stk.empty()) {
                int node = stk.top();
                stk.pop();
                cout << node + 1 << ' ';
                was[node] = true;
                if (node == x) {
                    break;
                }
            }
            cout << '\n';
        }
        stk.push(x);
        was[x] = true;
        for (; p[x] < (int)(g[x].size()); p[x]++) {
            int c = g[x][p[x]];
            if (removed[c]) {
                continue;
            }
            removed[c] = true;
            int nxt = (x ^ u[c] ^ v[c]);
            p[x]++; 
            dfs(nxt);
            return;
        }
        stk.pop();
        was[x] = false; 
    };
    for (int i = 0; i < n; i++) {
        dfs(i);
    }
    return 0;
}

Subtask #1
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Edge does not exist or used 2, 5
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Edge does not exist or used 2, 5
3 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Edge does not exist or used 2, 5
3 Halted 0 ms 0 KB -