oj.uz

Submission #227178

# Submission time Handle Problem Language Result Execution time Memory
227178 2020-04-26T10:52:49 Z tushar_2658 Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 94328 KB 
#include "bits/stdc++.h"
using namespace std;

const int maxn = 500005;
multiset<int> edges[maxn];
vector<int> path;

void dfs(int x){
	while(!edges[x].empty()){
		int i = *edges[x].begin();
		edges[x].erase(edges[x].find(i));
		edges[i].erase(edges[i].find(x));
		dfs(i);
	}
	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].insert(y); 
		edges[y].insert(x);
	}
	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

postmen.cpp: In function 'int main(int, const char**)':
postmen.cpp:22: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:25: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.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Correct 17 ms 23808 KB Output is correct
4 Correct 20 ms 24320 KB Output is correct
5 Correct 18 ms 23936 KB Output is correct
6 Correct 20 ms 24448 KB Output is correct
7 Correct 31 ms 25984 KB Output is correct
8 Correct 18 ms 24064 KB Output is correct
9 Correct 154 ms 37880 KB Output is correct
10 Correct 20 ms 24192 KB Output is correct
11 Correct 19 ms 24192 KB Output is correct
12 Correct 146 ms 37916 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Correct 18 ms 23808 KB Output is correct
4 Correct 23 ms 24320 KB Output is correct
5 Correct 18 ms 23936 KB Output is correct
6 Correct 21 ms 24448 KB Output is correct
7 Correct 32 ms 25984 KB Output is correct
8 Correct 21 ms 24064 KB Output is correct
9 Correct 148 ms 38008 KB Output is correct
10 Correct 20 ms 24192 KB Output is correct
11 Correct 19 ms 24064 KB Output is correct
12 Correct 141 ms 38008 KB Output is correct
13 Correct 108 ms 38008 KB Output is correct
14 Correct 121 ms 38008 KB Output is correct
15 Correct 136 ms 37940 KB Output is correct
16 Correct 113 ms 38028 KB Output is correct
17 Correct 129 ms 38008 KB Output is correct
18 Correct 117 ms 35060 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Correct 17 ms 23808 KB Output is correct
4 Correct 20 ms 24192 KB Output is correct
5 Correct 18 ms 23936 KB Output is correct
6 Correct 21 ms 24448 KB Output is correct
7 Correct 32 ms 25976 KB Output is correct
8 Correct 19 ms 24064 KB Output is correct
9 Correct 154 ms 37880 KB Output is correct
10 Correct 20 ms 24320 KB Output is correct
11 Correct 19 ms 24192 KB Output is correct
12 Correct 166 ms 38008 KB Output is correct
13 Correct 117 ms 38136 KB Output is correct
14 Correct 126 ms 38008 KB Output is correct
15 Correct 127 ms 38008 KB Output is correct
16 Correct 108 ms 38008 KB Output is correct
17 Correct 157 ms 38008 KB Output is correct
18 Correct 128 ms 35064 KB Output is correct
19 Execution timed out 586 ms 94328 KB Time limit exceeded
20 Halted 0 ms 0 KB -