oj.uz

답안 #88745

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
88745 2018-12-08T11:43:48 Z popovicirobert 어르신 집배원 (BOI14_postmen) C++14
55 / 100
 500 ms 55240 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const int MAXN = (int) 5e5;

vector <int> g[MAXN + 1];
pair <int, int> edges[MAXN + 1];
bool vis[MAXN + 1];
vector <int> ord;

void dfs(int nod) {
    while(g[nod].size()) {
        auto it = g[nod].back();
        g[nod].pop_back();
        if(vis[it] == 0) {
            vis[it] = 1;
            dfs(edges[it].first ^ edges[it].second ^ nod);
        }
    }
    ord.push_back(nod);
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, m;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        edges[i] = {x, y};
        g[x].push_back(i);
        g[y].push_back(i);
    }
    dfs(1);
    for(i = 1; i <= n; i++) {
        vis[i] = 0;
    }
    int sz = ord.size();
    vector <int> stk;
    for(i = 0; i < sz; i++) {
        if(vis[ord[i]] == 0) {
            vis[ord[i]] = 1;
            stk.push_back(ord[i]);
        }
        else {
            while(stk.back() != ord[i]) {
                cout << stk.back() << " ";
                vis[stk.back()] = 0;
                stk.pop_back();
            }
            cout << ord[i] << "\n";
        }
    }
    //cout << ans;
    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 12160 KB Output is correct
2 Correct 12 ms 12032 KB Output is correct
3 Correct 11 ms 12080 KB Output is correct
4 Correct 13 ms 12288 KB Output is correct
5 Correct 13 ms 12160 KB Output is correct
6 Correct 14 ms 12468 KB Output is correct
7 Correct 18 ms 13184 KB Output is correct
8 Correct 12 ms 12288 KB Output is correct
9 Correct 45 ms 18032 KB Output is correct
10 Correct 12 ms 12288 KB Output is correct
11 Correct 15 ms 12288 KB Output is correct
12 Correct 51 ms 18264 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 12160 KB Output is correct
2 Correct 12 ms 12160 KB Output is correct
3 Correct 13 ms 12032 KB Output is correct
4 Correct 13 ms 12288 KB Output is correct
5 Correct 12 ms 12160 KB Output is correct
6 Correct 14 ms 12416 KB Output is correct
7 Correct 16 ms 13056 KB Output is correct
8 Correct 13 ms 12288 KB Output is correct
9 Correct 45 ms 18032 KB Output is correct
10 Correct 14 ms 12288 KB Output is correct
11 Correct 12 ms 12288 KB Output is correct
12 Correct 52 ms 18160 KB Output is correct
13 Correct 96 ms 20720 KB Output is correct
14 Correct 88 ms 18292 KB Output is correct
15 Correct 79 ms 19440 KB Output is correct
16 Correct 95 ms 20724 KB Output is correct
17 Correct 85 ms 16624 KB Output is correct
18 Correct 89 ms 18928 KB Output is correct

Subtask #3
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 12160 KB Output is correct
2 Correct 12 ms 12032 KB Output is correct
3 Correct 12 ms 12160 KB Output is correct
4 Correct 13 ms 12416 KB Output is correct
5 Correct 14 ms 12160 KB Output is correct
6 Correct 13 ms 12416 KB Output is correct
7 Correct 18 ms 13056 KB Output is correct
8 Correct 13 ms 12288 KB Output is correct
9 Correct 45 ms 18032 KB Output is correct
10 Correct 15 ms 12288 KB Output is correct
11 Correct 13 ms 12288 KB Output is correct
12 Correct 57 ms 18264 KB Output is correct
13 Correct 98 ms 20736 KB Output is correct
14 Correct 88 ms 18392 KB Output is correct
15 Correct 85 ms 19492 KB Output is correct
16 Correct 97 ms 20800 KB Output is correct
17 Correct 82 ms 16624 KB Output is correct
18 Correct 83 ms 19008 KB Output is correct
19 Execution timed out 551 ms 55240 KB Time limit exceeded
20 Halted 0 ms 0 KB -