Submission #227183

#	Time	Username	Problem	Language	Result	Execution time	Memory
227183		tushar_2658	Senior Postmen (BOI14_postmen)	C++14	55 / 100	527 ms	58856 KiB

postmen

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

const int maxn = 500005;
vector<pair<int, int>> edges[maxn];
int used[maxn]; 
vector<int> path;

void dfs(int x){
	while(!edges[x].empty()){
		pair<int, int> i = edges[x].back();
		edges[x].pop_back();
		if(used[i.second] == 0){
			used[i.second] = 1;
			dfs(i.first);
		}
	}
	path.push_back(x);
}

int main(int argc, char const *argv[])
{
//	freopen("in.txt", "r", stdin); 
	int n, m;
	scanf("%d %d", &n, &m); 
	for(int i = 0; i < m; ++i){
		int x, y;
		scanf("%d %d", &x, &y); 
		edges[x].push_back(make_pair(y, i)); 
		edges[y].push_back(make_pair(x, i));
	}
	dfs(1);
	path.pop_back();
	vector<vector<int>> ans;
	vector<bool> vis(n + 1, 0);
	stack<int> st;
	vector<int> v;
	for(auto i : path){
		if(vis[i]){
			v.clear();
			while(st.top() != i){
				v.push_back(st.top());
				vis[st.top()] = 0;
				st.pop();
			}
			if(st.top() == i){
				vis[st.top()] = 0;
				v.push_back(st.top());
				st.pop();
			}
			ans.push_back(v);
		}
		vis[i] = 1;
		st.push(i);
	}
	v.clear();
	while(!st.empty()){
		v.push_back(st.top());
		st.pop();
	}
	ans.push_back(v);
	for(auto i : ans){
		for(auto j : i){
			printf("%d ", j);
		}
		printf("\n");
	}

	return 0;
}

Compilation message (stderr)

postmen.cpp: In function 'int main(int, const char**)':
postmen.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m); 
  ~~~~~^~~~~~~~~~~~~~~~~
postmen.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y); 
   ~~~~~^~~~~~~~~~~~~~~~~

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