Submission #880005

#	Time	Username	Problem	Language	Result	Execution time	Memory
880005		Karoot	Senior Postmen (BOI14_postmen)	C++17	100 / 100	331 ms	99648 KiB

postmen

#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
 
#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()
 
using namespace std;
 
typedef long long ll;
 
ll linf = 1e15+1;
 
inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}
 
const int MAXN = 5e5+1;
bool edgeVisited[MAXN];
vector<pair<int, int>> adj[MAXN];
bool isVisited[MAXN];
int startNode;
int neighIndex[MAXN];
 
vector<vector<int> > sols;
vector<int> temp;
 
int counter = 0;
//Destination, ID
 
bool dfs(int node, int usedEdge){
    edgeVisited[usedEdge] = true;
    if (isVisited[node]){
        startNode = node;
        return true;
    }
 
    //counter++;
 
    isVisited[node] = true;
    //cout << node << ": " << usedEdge << endl;
    while (neighIndex[node] < adj[node].size()){
        pair<int, int> e = adj[node][neighIndex[node]++];
        if (!edgeVisited[e.second]){
            bool ret = dfs(e.first, e.second);
            if (ret){
                temp.push_back(node);
                //hasEdges[node] -= 2;
                if (node == startNode){
                    sols.push_back(temp);
                    temp.clear();
                } else {
                    isVisited[node] = false;
                    return true;
                }
            }
        } else {
            counter++;
        }
    }
 
    isVisited[node] = false;
    return false;
}
 
int main(){
    scoobydoobydoo();
    //freopen("seniorPostmen.in", "r", stdin);
    //freopen("seniorPostmen.ans", "w", stdout);
    int n, m; cin >> n >> m;
 
    for (int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back({b, i+1});
        adj[b].push_back({a, i+1});
    }
 
    //cout << maxi << endl
 
 
    
    for (int i = 1; i <= n; i++){
        if (!isVisited[i])dfs(i, 0);
    }
 
    //cout << counter << "\n";
 
    for (auto& v : sols){
        for (auto& e : v){
            cout << e << " ";
        }
        cout << "\n";
    }
    
 
 
 
    return 0;
}

Compilation message (stderr)

postmen.cpp: In function 'bool dfs(int, int)':
postmen.cpp:51:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     while (neighIndex[node] < adj[node].size()){
      |            ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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