oj.uz

답안 #421634

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
421634 2021-06-09T10:14:39 Z EleCursity 어르신 집배원 (BOI14_postmen) C++14
100 / 100
 354 ms 30488 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]
   75 |  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]
   77 |   scanf("%d%d", &E[i][0], &E[i][1]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 6 ms 716 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 48 ms 3292 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 41 ms 3608 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 304 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 8 ms 716 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 39 ms 3396 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 2 ms 456 KB Output is correct
12 Correct 42 ms 3580 KB Output is correct
13 Correct 62 ms 5956 KB Output is correct
14 Correct 60 ms 5200 KB Output is correct
15 Correct 45 ms 4676 KB Output is correct
16 Correct 58 ms 5952 KB Output is correct
17 Correct 49 ms 5044 KB Output is correct
18 Correct 61 ms 5300 KB Output is correct

Subtask #3
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 444 KB Output is correct
7 Correct 6 ms 716 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 48 ms 3380 KB Output is correct
10 Correct 3 ms 448 KB Output is correct
11 Correct 2 ms 456 KB Output is correct
12 Correct 54 ms 3584 KB Output is correct
13 Correct 48 ms 5956 KB Output is correct
14 Correct 47 ms 5168 KB Output is correct
15 Correct 52 ms 4744 KB Output is correct
16 Correct 57 ms 6056 KB Output is correct
17 Correct 49 ms 5048 KB Output is correct
18 Correct 53 ms 5320 KB Output is correct
19 Correct 303 ms 30316 KB Output is correct
20 Correct 314 ms 26168 KB Output is correct
21 Correct 354 ms 23124 KB Output is correct
22 Correct 298 ms 30488 KB Output is correct
23 Correct 240 ms 15808 KB Output is correct
24 Correct 350 ms 25032 KB Output is correct
25 Correct 302 ms 26444 KB Output is correct