oj.uz

답안 #364632

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
364632 2021-02-09T15:26:51 Z LucaDantas 어르신 집배원 (BOI14_postmen) C++17
100 / 100
 408 ms 34220 KB 
#include<iostream>
#include<vector>
#include <cassert>
#include<utility>
using namespace std;

#define pb push_back
#define sz(a) (int)(a.size())

constexpr int maxn = 5e5+10;

vector<pair<int,int>> g[maxn];
vector<int> st;

bool mark[maxn], mark_edge[maxn];

int rd() {
	int result = 0;
	char ch;
	ch = getchar();
	while(ch < '0' || ch > '9') ch = getchar();
	result = ch-'0';
	while (true) {
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		result = result*10 + (ch - '0');
	}
	return result;
}

void dfs(int i) {
	st.pb(i);
	while(1) {
		int u = st.back();
		mark[u] = 1;

		while(g[u].size() && mark_edge[g[u].back().second])
			g[u].pop_back();

		if(!sz(g[u])) break;

		int v = g[u].back().first;
		mark_edge[g[u].back().second] = 1;
		g[u].pop_back();

		if(mark[v]) {
			printf("%d", v);
			while(st.size() && st.back() != v) {
				printf(" %d", st.back());
				mark[st.back()] = 0;
				st.pop_back();
			}
			printf("\n");
		}
		else st.pb(v);
	}
	mark[i] = 0;
	st.clear();
}

int main() {
	int n = rd(), m = rd();
	for(int i = 0, a, b; i < m; i++)
		a=rd(), b=rd(), g[a].pb({b, i}), g[b].pb({a, i});
	for(int i = 1; i <= n; i++)
		dfs(i);
}

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12012 KB Output is correct
2 Correct 8 ms 12012 KB Output is correct
3 Correct 8 ms 12140 KB Output is correct
4 Correct 9 ms 12140 KB Output is correct
5 Correct 8 ms 12140 KB Output is correct
6 Correct 9 ms 12268 KB Output is correct
7 Correct 11 ms 12652 KB Output is correct
8 Correct 8 ms 12140 KB Output is correct
9 Correct 30 ms 14572 KB Output is correct
10 Correct 9 ms 12140 KB Output is correct
11 Correct 9 ms 12140 KB Output is correct
12 Correct 31 ms 14956 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12012 KB Output is correct
2 Correct 8 ms 12012 KB Output is correct
3 Correct 8 ms 12012 KB Output is correct
4 Correct 10 ms 12140 KB Output is correct
5 Correct 9 ms 12140 KB Output is correct
6 Correct 9 ms 12268 KB Output is correct
7 Correct 11 ms 12652 KB Output is correct
8 Correct 9 ms 12140 KB Output is correct
9 Correct 29 ms 14572 KB Output is correct
10 Correct 10 ms 12140 KB Output is correct
11 Correct 9 ms 12140 KB Output is correct
12 Correct 32 ms 14956 KB Output is correct
13 Correct 66 ms 16492 KB Output is correct
14 Correct 45 ms 15724 KB Output is correct
15 Correct 54 ms 15328 KB Output is correct
16 Correct 64 ms 16492 KB Output is correct
17 Correct 60 ms 15596 KB Output is correct
18 Correct 52 ms 15980 KB Output is correct

Subtask #3
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12012 KB Output is correct
2 Correct 8 ms 12012 KB Output is correct
3 Correct 8 ms 12012 KB Output is correct
4 Correct 9 ms 12140 KB Output is correct
5 Correct 8 ms 12268 KB Output is correct
6 Correct 9 ms 12268 KB Output is correct
7 Correct 12 ms 12652 KB Output is correct
8 Correct 9 ms 12140 KB Output is correct
9 Correct 31 ms 14848 KB Output is correct
10 Correct 9 ms 12140 KB Output is correct
11 Correct 9 ms 12140 KB Output is correct
12 Correct 31 ms 14956 KB Output is correct
13 Correct 57 ms 16492 KB Output is correct
14 Correct 52 ms 15724 KB Output is correct
15 Correct 49 ms 15328 KB Output is correct
16 Correct 70 ms 16492 KB Output is correct
17 Correct 55 ms 15724 KB Output is correct
18 Correct 56 ms 15980 KB Output is correct
19 Correct 381 ms 34140 KB Output is correct
20 Correct 394 ms 30700 KB Output is correct
21 Correct 326 ms 28564 KB Output is correct
22 Correct 403 ms 34220 KB Output is correct
23 Correct 151 ms 23404 KB Output is correct
24 Correct 408 ms 29932 KB Output is correct
25 Correct 399 ms 31332 KB Output is correct