oj.uz

Submission #107750

# Submission time Handle Problem Language Result Execution time Memory
107750 2019-04-25T15:42:50 Z dfistric Senior Postmen (BOI14_postmen) C++14
100 / 100
 429 ms 23800 KB 
/*
Official solution for postmen. 
Complexity O(N + M)
Author: Kestutis Vilcinskas
*/
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
const int MaxN = 500010,
	  	  MaxM = 2*500010;


int E[MaxM][3];
int pr[MaxN] = {0};

int P[MaxN], tmp[MaxN] = {0}, C[MaxN];
int k[MaxM];

int N, M, a, b;

bool visited[MaxN] = {0};
vector<int> path;

int newv = -1, u;

int getU (int i, int v) {
	return (v == E[i][0]) ? E[i][1] : E[i][0];
}


void dfs(int v) {
	path.clear();
	path.push_back(v);	
	while (v != -1) {
		//printf("V = %d!!!\n", v);
		visited[v] = true;
		newv = -1;
		for (; pr[v] < C[v]; pr[v]++) {
			int i = k[P[v] + pr[v]];
				if (E[i][2] == false) {
					u = getU(i, v);
					E[i][2] = true;
					if (visited[u]) {
						newv = u;
						while (path.back() != u) {
						       	printf("%d ", path.back());
							visited[path.back()] = false;
							path.pop_back();
						}
						printf("%d\n", path.back());
					}else {
						newv = u;
						path.push_back(u);
					}
					break;
				}
		}
		if (newv == -1 and path.size() > 1) {
			newv = path.back();
			path.pop_back();
		}
		v =newv;
	}
	visited[path[0]] = false;
	//for (int i = 0; i < path.size(); i++)
	//	visited[path[i]] = false;
}



int main() {
	path.reserve(MaxN);	
	scanf("%d%d\n", &N, &M);
	for (int i = 0; i < M; i++) {
		scanf("%d%d", &E[i][0], &E[i][1]);
		C[E[i][0]]++;
		C[E[i][1]]++;
	}
    
	P[1] = 0;
	for (int i = 2; i <= N; i++) {
		P[i] = P[i-1] + C[i-1];
	}
	for (int i = 0; i < M; i++) {
		a = E[i][0]; b = E[i][1];
		k[P[a] + tmp[a]] = i;
		k[P[b] + tmp[b]] = i;
		tmp[a]++;
		tmp[b]++;
	}
	for (int i = 1; i <= N; i++) {
		dfs(i);
		
		}
	return 0;
}

Compilation message

postmen.cpp: In function 'int main()':
postmen.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d\n", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~~
postmen.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &E[i][0], &E[i][1]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 360 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 24 ms 768 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 42 ms 2680 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 46 ms 2808 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 8 ms 512 KB Output is correct
7 Correct 10 ms 768 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 52 ms 2680 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 7 ms 512 KB Output is correct
12 Correct 43 ms 2808 KB Output is correct
13 Correct 53 ms 4984 KB Output is correct
14 Correct 54 ms 4192 KB Output is correct
15 Correct 52 ms 3832 KB Output is correct
16 Correct 52 ms 4984 KB Output is correct
17 Correct 60 ms 4028 KB Output is correct
18 Correct 52 ms 4216 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 360 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 12 ms 512 KB Output is correct
7 Correct 10 ms 672 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 41 ms 2680 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 7 ms 512 KB Output is correct
12 Correct 44 ms 2812 KB Output is correct
13 Correct 65 ms 4984 KB Output is correct
14 Correct 49 ms 4216 KB Output is correct
15 Correct 47 ms 3960 KB Output is correct
16 Correct 54 ms 4984 KB Output is correct
17 Correct 52 ms 3960 KB Output is correct
18 Correct 50 ms 4216 KB Output is correct
19 Correct 368 ms 23788 KB Output is correct
20 Correct 328 ms 19696 KB Output is correct
21 Correct 333 ms 18292 KB Output is correct
22 Correct 335 ms 23800 KB Output is correct
23 Correct 207 ms 12152 KB Output is correct
24 Correct 429 ms 18812 KB Output is correct
25 Correct 336 ms 20108 KB Output is correct