oj.uz

Submission #116052

# Submission time Handle Problem Language Result Execution time Memory
116052 2019-06-10T09:37:53 Z MAMBA Senior Postmen (BOI14_postmen) C++17
100 / 100
 340 ms 41084 KB 
#include <bits/stdc++.h> 

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
typedef vector<int> vi;

constexpr int N = 5e5 + 10;

int n, m, a, b;

int ptr[N];
bitset<N> mark, mark2;

int shit, to[N << 1], pre[N << 1], last[N << 1], junk[N << 1];

inline void addEdge(int a , int b) {
	to[shit] = b; pre[shit] = last[a]; last[a] = shit++;
	to[shit] = a; pre[shit] = last[b]; last[b] = shit++;	
}

int st[N], R;
void dfs(int v) {
	while (last[v] != -1) {
		int id = last[v];
		last[v] = pre[id];
		if (!mark[id / 2]) {
			mark[id / 2] = true;
			dfs(to[id]);
		}
	}
	if (mark2[v]) {
		while (mark2[v]) {
			printf("%d" , st[R]);
			if (st[R] == v) printf("\n");
			else printf(" ");
			mark2[st[R]] = false;
			R--;
		}
	} 
	mark2[v] = true;
	st[++R] = v;

}

int main() {
	memset(last, -1, sizeof(last));
	scanf("%d%d" , &n , &m);
	rep(i , 0 , m) {
		scanf("%d%d" , &a , &b);
		addEdge(a , b);
	}

	dfs(1);

	return 0;
}

Compilation message

postmen.cpp: In function 'int main()':
postmen.cpp:49: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:51:8: 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.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4224 KB Output is correct
2 Correct 7 ms 4352 KB Output is correct
3 Correct 7 ms 4224 KB Output is correct
4 Correct 8 ms 4480 KB Output is correct
5 Correct 7 ms 4352 KB Output is correct
6 Correct 10 ms 4608 KB Output is correct
7 Correct 13 ms 5248 KB Output is correct
8 Correct 8 ms 4352 KB Output is correct
9 Correct 56 ms 10900 KB Output is correct
10 Correct 9 ms 4352 KB Output is correct
11 Correct 7 ms 4352 KB Output is correct
12 Correct 64 ms 11128 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4224 KB Output is correct
2 Correct 8 ms 4200 KB Output is correct
3 Correct 7 ms 4224 KB Output is correct
4 Correct 10 ms 4480 KB Output is correct
5 Correct 7 ms 4404 KB Output is correct
6 Correct 8 ms 4480 KB Output is correct
7 Correct 12 ms 5248 KB Output is correct
8 Correct 8 ms 4352 KB Output is correct
9 Correct 47 ms 10872 KB Output is correct
10 Correct 8 ms 4352 KB Output is correct
11 Correct 9 ms 4480 KB Output is correct
12 Correct 49 ms 11000 KB Output is correct
13 Correct 81 ms 11500 KB Output is correct
14 Correct 51 ms 8952 KB Output is correct
15 Correct 51 ms 11000 KB Output is correct
16 Correct 49 ms 11512 KB Output is correct
17 Correct 59 ms 6776 KB Output is correct
18 Correct 52 ms 10104 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4224 KB Output is correct
2 Correct 8 ms 4352 KB Output is correct
3 Correct 8 ms 4224 KB Output is correct
4 Correct 17 ms 4456 KB Output is correct
5 Correct 7 ms 4352 KB Output is correct
6 Correct 11 ms 4608 KB Output is correct
7 Correct 12 ms 5248 KB Output is correct
8 Correct 7 ms 4352 KB Output is correct
9 Correct 44 ms 10872 KB Output is correct
10 Correct 11 ms 4352 KB Output is correct
11 Correct 7 ms 4352 KB Output is correct
12 Correct 54 ms 11012 KB Output is correct
13 Correct 68 ms 11488 KB Output is correct
14 Correct 51 ms 9080 KB Output is correct
15 Correct 54 ms 11000 KB Output is correct
16 Correct 66 ms 11512 KB Output is correct
17 Correct 52 ms 6776 KB Output is correct
18 Correct 61 ms 10060 KB Output is correct
19 Correct 327 ms 41084 KB Output is correct
20 Correct 332 ms 28284 KB Output is correct
21 Correct 293 ms 38196 KB Output is correct
22 Correct 316 ms 41032 KB Output is correct
23 Correct 209 ms 37472 KB Output is correct
24 Correct 335 ms 17528 KB Output is correct
25 Correct 340 ms 33516 KB Output is correct