oj.uz

답안 #636295

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
636295 2022-08-28T20:46:36 Z tvladm2009 어르신 집배원 (BOI14_postmen) C++14
100 / 100
 402 ms 71312 KB 
#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 5 * 1e5;
int in[MAX_N + 1], out[MAX_N + 1];
vector<int> g[MAX_N + 1], aux;
bool viz[MAX_N + 1], b[MAX_N + 1];
int n, m;

void dfs(int u) {
	while (g[u].size()) {
		int v = g[u].back();
		g[u].pop_back();
		if (viz[v]) {
			continue;
        }
		viz[v] = 1;
		dfs(in[v] ^ out[v] ^ u);
		aux.push_back(u);
	}
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> in[i] >> out[i];
        in[i]--;
        out[i]--;
        g[in[i]].push_back(i);
        g[out[i]].push_back(i);
    }
    aux.push_back(0);
    dfs(0);
    vector<int> sol;
    for (int it : aux) {
        if (b[it] == true) {
            while (b[it] == true) {
                cout << sol.back() + 1 << " ";
                b[sol.back()] = false;
                sol.pop_back();
            }
            cout << "\n";
        }
        b[it] = true;
        sol.push_back(it);
    }
    return 0;
}

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 11964 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 7 ms 12336 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 7 ms 12500 KB Output is correct
7 Correct 12 ms 13584 KB Output is correct
8 Correct 8 ms 12244 KB Output is correct
9 Correct 35 ms 21076 KB Output is correct
10 Correct 7 ms 12244 KB Output is correct
11 Correct 7 ms 12244 KB Output is correct
12 Correct 39 ms 21316 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 8 ms 12424 KB Output is correct
5 Correct 8 ms 12116 KB Output is correct
6 Correct 8 ms 12544 KB Output is correct
7 Correct 11 ms 13524 KB Output is correct
8 Correct 7 ms 12244 KB Output is correct
9 Correct 35 ms 21000 KB Output is correct
10 Correct 9 ms 12244 KB Output is correct
11 Correct 7 ms 12244 KB Output is correct
12 Correct 38 ms 21272 KB Output is correct
13 Correct 53 ms 23840 KB Output is correct
14 Correct 48 ms 19908 KB Output is correct
15 Correct 53 ms 22608 KB Output is correct
16 Correct 56 ms 23964 KB Output is correct
17 Correct 50 ms 16980 KB Output is correct
18 Correct 55 ms 21188 KB Output is correct

Subtask #3
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 11968 KB Output is correct
3 Correct 6 ms 12020 KB Output is correct
4 Correct 7 ms 12372 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 7 ms 12500 KB Output is correct
7 Correct 12 ms 13580 KB Output is correct
8 Correct 7 ms 12244 KB Output is correct
9 Correct 35 ms 21012 KB Output is correct
10 Correct 7 ms 12244 KB Output is correct
11 Correct 7 ms 12244 KB Output is correct
12 Correct 39 ms 21316 KB Output is correct
13 Correct 53 ms 23944 KB Output is correct
14 Correct 51 ms 19952 KB Output is correct
15 Correct 50 ms 22536 KB Output is correct
16 Correct 55 ms 23880 KB Output is correct
17 Correct 50 ms 16960 KB Output is correct
18 Correct 53 ms 21276 KB Output is correct
19 Correct 387 ms 71256 KB Output is correct
20 Correct 354 ms 51632 KB Output is correct
21 Correct 341 ms 64616 KB Output is correct
22 Correct 394 ms 71312 KB Output is correct
23 Correct 179 ms 56208 KB Output is correct
24 Correct 402 ms 36480 KB Output is correct
25 Correct 390 ms 58476 KB Output is correct