Submission #292203

#	Time	Username	Problem	Language	Result	Execution time	Memory
292203		davooddkareshki	Senior Postmen (BOI14_postmen)	C++17	55 / 100	1056 ms	103932 KiB

postmen

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define mpr make_pair

typedef long long ll;
//typedef long double ld;

const int maxn = 5e5+10;
const int mod = 1e9+7;
const int inf = (1ll<<40)-1;

int n, m, k;
bool mark_E[maxn];
vector<pii> g[maxn];
int ptr[maxn];

int mark[maxn];
vector<int> stk;
vector<int> ans[maxn]; int num = 0;
vector<int> euler;
void dfs(int v)
{
    for(; ptr[v] < g[v].size(); ptr[v]++)
    {
        pii e = g[v][ptr[v]];
        int u = e.F, id = e.S;
        if(!mark_E[id])
        {
            mark_E[id] = 1;
            dfs(u);
            euler.push_back(u);
        }
    }
}

signed main()
{
    //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin>> n >> m;
    for(int i = 1, u, v; i <= m; i++)
    {
        cin>> u >> v;
        g[u].push_back({v,i});
        g[v].push_back({u,i});
    }

    dfs(1);
    euler.push_back(1);

    for(auto v : euler)
    {
        //cout<< v <<" ";
        if(mark[v])
        {
            num++;
            while(stk.back() != v)
            {
                int u = stk.back();
                mark[u] = 0;
                ans[num].push_back(u);
                stk.pop_back();
            }
            mark[v] = 0;
            ans[num].push_back(v);
            stk.pop_back();
        }
        mark[v] = 1;
        stk.push_back(v);
    }

   // cout<<"\n";
    for(int i = 1; i <= num; i++)
    {
        for(auto v : ans[i]) cout<< v <<" ";
        cout<<"\n";
    }
}
/*
10 15
1 3
5 1
2 3
9 2
3 4
6 3
4 5
7 4
4 8
5 7
8 5
6 7
7 8
8 10
10 9
*/

Compilation message (stderr)

postmen.cpp: In function 'void dfs(long long int)':
postmen.cpp:28:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(; ptr[v] < g[v].size(); ptr[v]++)
      |           ~~~~~~~^~~~~~~~~~~~~

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