Submission #1173333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173333		InvMOD	Senior Postmen (BOI14_postmen)	C++20	100 / 100	271 ms	107784 KiB

postmen

#include<bits/stdc++.h>

using namespace std;

#define sz(v) (int)(v).size()

/*
    A cycle:
    + will start in the same node and end in the same node
    + never pass a node >= 2 times

    We need some cycles:
    + will cover all Edges

    We had:
    + N <= 5 * 10^5, M <= 5 * 10 ^ 5
    + call deg[x] => deg[x] always % 2 == 0

    - After we take away a cycle, all node in that cycle has there deg -= 2
    - If some of them still has deg -> there still be a cycle that can go through it
    - (if we can go from u -> v, v will always has some edges to another node x)
    - (if v is a node in cycle that don't has u there will also always edges that we can go to another node y)
      + Because all deg[x] % 2 == 0, if we has two edges from cycle contain v but does not contain u,
        if there is only 1 from u -> v, it will become -1 (we had that deg[x] % 2 always = 0)
    - So we will DFS and delete some cycle
    - Time complexity: O(n * how to delete edges)
*/

void solve()
{
    int n,m; cin >> n >> m;

    vector<vector<int>> adj(n + 1, vector<int>());
    vector<pair<int,int>> E(m + 1);
    for(int i = 1; i <= m; i++){
        int u,v; cin >> u >> v;
        adj[u].push_back(i);
        adj[v].push_back(i);
        E[i] = make_pair(u, v);
    }

    vector<bool> vis(n + 1, false), del(m + 1, false);

    stack<int> node;

    function<void(int)> dfs = [&](int x) -> void{
        if(vis[x]){
            int cur_node;
            do{
                cur_node = node.top(); node.pop();
                vis[cur_node] = false;
                cout << cur_node <<" ";
            } while(cur_node != x);
            cout << "\n";
        }

        while(sz(adj[x])){
            int id = adj[x].back(); adj[x].pop_back();

            if(del[id]) continue; del[id] = true;

            int v = E[id].first ^ E[id].second ^ x;
            node.push(x); vis[x] = true;
            dfs(v);
        }
        return;
    };

    for(int i = 1; i <= n; i++){
        if(sz(adj[i])) dfs(i);
    }

//    if(sz(node)){
//        cout << "DUMB\n";
//    }
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    solve();
    return 0;
}

Compilation message (stderr)

postmen.cpp: In function 'int32_t main()':
postmen.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
postmen.cpp:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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