Submission #129873

#	Time	Username	Problem	Language	Result	Execution time	Memory
129873		davitmarg	Senior Postmen (BOI14_postmen)	C++17	55 / 100	575 ms	52864 KiB

postmen

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;;
int n,m;
int used[500005],edge[500005];
vector<pair<int,int>> g[500005];
vector<int> path;

void euler(int v)
{
    while(!g[v].empty())
	{
		int to=g[v].back().first;
		int id=g[v].back().second;
        g[v].pop_back();
        if(used[id])
			continue;
        used[id]=1;
        euler(to);
	}
	path.PB(v);
}

void add(int a,int b,int id)
{
	g[a].PB(MP(b,id));
	g[b].PB(MP(a,id));
}

void print(vector<int> &s)
{
    while(!s.empty())
	{
        printf("%d ",s.back());
        s.pop_back();
	}
    printf("\n");
}

int main()
{
    cin >> n >> m;
	while(m--)
	{
        int a,b;
        scanf("%d%d",&a,&b);
		add(a,b,m);
	}
    euler(1);

    vector<int> s;
    for(int i=0;i<=n;i++)
        used[i]=0;
    for(int i=0;i<path.size();i++)
	{
        if(!used[path[i]])
        {
            s.PB(path[i]);
            used[path[i]]=1;
        }
        else
		{
			printf("%d ",path[i]);
            while(s.back()!=path[i])
			{
				printf("%d ",s.back());
                used[s.back()]=0;
                s.pop_back();
			}
            printf("\n");
		}
	}

    return 0;
}


/*

6 6
1 2
1 3
1 4
1 5
3 2
4 5



*/

Compilation message (stderr)

postmen.cpp: In function 'int main()':
postmen.cpp:74:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<path.size();i++)
                 ~^~~~~~~~~~~~
postmen.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~

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