oj.uz

Submission #374307

# Submission time Handle Problem Language Result Execution time Memory
374307 2021-03-07T07:30:58 Z abra_stone Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 93604 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#define N 500005
using namespace std;

int n, m;
bool v[N], vi[N];
vector<int> gr[N], gi[N], ans;
stack<int> st;

void f(int p) {
	int i;
	while (gr[p].size() > 0) {
		int ne = gr[p].back(), ni = gi[p].back();
		gr[p].pop_back(); gi[p].pop_back();
		if (vi[ni]) continue;
		vi[ni] = 1;
		f(ne);
	}
	ans.push_back(p);
}

int main()
{
	int i, t1, t2;
	cin >> n >> m;
	for (i = 0; i < m; i++) {
		scanf("%d %d", &t1, &t2);
		gr[t1].push_back(t2); gi[t1].push_back(i);
		gr[t2].push_back(t1); gi[t2].push_back(i);
	}
	f(1);
	for (i = 0; i < ans.size(); i++) {
		if (v[ans[i]]) {
			printf("%d ", ans[i]);
			while (!st.empty()) {
				int tp = st.top();
				if (tp == ans[i]) break;
				st.pop();
				v[tp] = 0;
				printf("%d ", tp);
			}
			puts("");
		} else {
			v[ans[i]] = 1;
			st.push(ans[i]);
		}
	}
    return 0;
}

Compilation message

postmen.cpp: In function 'void f(int)':
postmen.cpp:14:6: warning: unused variable 'i' [-Wunused-variable]
   14 |  int i;
      |      ^
postmen.cpp: In function 'int main()':
postmen.cpp:35:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for (i = 0; i < ans.size(); i++) {
      |              ~~^~~~~~~~~~~~
postmen.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |   scanf("%d %d", &t1, &t2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 17 ms 23788 KB Output is correct
3 Correct 17 ms 23788 KB Output is correct
4 Correct 18 ms 24172 KB Output is correct
5 Correct 17 ms 23916 KB Output is correct
6 Correct 19 ms 24300 KB Output is correct
7 Correct 24 ms 25324 KB Output is correct
8 Correct 18 ms 24044 KB Output is correct
9 Correct 65 ms 32228 KB Output is correct
10 Correct 18 ms 24044 KB Output is correct
11 Correct 19 ms 24044 KB Output is correct
12 Correct 70 ms 32740 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 16 ms 23788 KB Output is correct
3 Correct 19 ms 23788 KB Output is correct
4 Correct 18 ms 24172 KB Output is correct
5 Correct 17 ms 23916 KB Output is correct
6 Correct 19 ms 24300 KB Output is correct
7 Correct 24 ms 25324 KB Output is correct
8 Correct 18 ms 24044 KB Output is correct
9 Correct 64 ms 32228 KB Output is correct
10 Correct 18 ms 24044 KB Output is correct
11 Correct 19 ms 24044 KB Output is correct
12 Correct 73 ms 32740 KB Output is correct
13 Correct 142 ms 37592 KB Output is correct
14 Correct 115 ms 33388 KB Output is correct
15 Correct 118 ms 35472 KB Output is correct
16 Correct 126 ms 37604 KB Output is correct
17 Correct 135 ms 31208 KB Output is correct
18 Correct 125 ms 34488 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 18 ms 24044 KB Output is correct
3 Correct 18 ms 23788 KB Output is correct
4 Correct 18 ms 24172 KB Output is correct
5 Correct 17 ms 23916 KB Output is correct
6 Correct 19 ms 24300 KB Output is correct
7 Correct 24 ms 25324 KB Output is correct
8 Correct 18 ms 24044 KB Output is correct
9 Correct 65 ms 32228 KB Output is correct
10 Correct 21 ms 24172 KB Output is correct
11 Correct 18 ms 24044 KB Output is correct
12 Correct 71 ms 32740 KB Output is correct
13 Correct 147 ms 37604 KB Output is correct
14 Correct 120 ms 33516 KB Output is correct
15 Correct 117 ms 35296 KB Output is correct
16 Correct 130 ms 37604 KB Output is correct
17 Correct 145 ms 31208 KB Output is correct
18 Correct 128 ms 34452 KB Output is correct
19 Execution timed out 737 ms 93604 KB Time limit exceeded
20 Halted 0 ms 0 KB -