Submission #866326

#	Time	Username	Problem	Language	Result	Execution time	Memory
866326		BBart888	Senior Postmen (BOI14_postmen)	C++14	0 / 100	34 ms	144728 KiB

postmen

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <queue>
#include <map>
#include <iomanip>
#include <stack>
#include <stdio.h>      
#include <stdlib.h>     
#include <time.h> 
#include <string>
#include <fstream>



using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;



using Mat = vector<vector<ll>>;
const ll MOD = 1e9 + 7;
const int MAXN = 3e6 + 11;

int n, m;
vector<pair<int, int>> adj[MAXN];
bool used[MAXN];
vector<int> path;
vector<int> ans[MAXN];
int index;
bool vis[MAXN];
int prv[MAXN];

void dfs(int v)
{
    while (!adj[v].empty())
    {
        auto u = adj[v].back();
        adj[v].pop_back();
        if (used[u.second] || vis[u.first])
            continue;
        used[u.second] = true;
        dfs(u.first);
    }
    path.push_back(v);
}



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);



    //freopen("exercise.in", "r", stdin);
    //freopen("exercise.out", "w", stdout);

    
    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back({ b ,i});
        adj[b].push_back({ a ,i});
    }

    


    dfs(1);

    for (int i = 1; i < path.size(); i++)
        prv[i] = i - 1;


    for (int i = 0; i < path.size(); i++)
    {
        int v = path[i];

        if (vis[v])
        {
           
            //cout << i << " ";
            int curr = prv[i];
            while (path[curr] != v)
            {
                ans[index].push_back(path[curr]);
                //cout << curr << " ";
                vis[path[curr]] = false;
                curr = prv[curr];
            }
            ans[index].push_back(path[curr]);
            //cout << curr << " ";
            prv[i] = curr-1;
            reverse(ans[index].begin(), ans[index].end());
            index++;
        }
        else
            vis[v] = true;
        
        //cout << '\n';
    }

    
    for (int i = 0; i < index; i++)
    {
        for (auto v : ans[i])
            cout << v << " ";
        cout << '\n';
    }







    return 0;
}

Compilation message (stderr)

postmen.cpp: In function 'int main()':
postmen.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int i = 1; i < path.size(); i++)
      |                     ~~^~~~~~~~~~~~~
postmen.cpp:85:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (int i = 0; i < path.size(); i++)
      |                     ~~^~~~~~~~~~~~~

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