oj.uz

답안 #88744

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
88744 2018-12-08T11:41:05 Z popovicirobert 어르신 집배원 (BOI14_postmen) C++14
55 / 100
 500 ms 51496 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 < pair <int, int> > g[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.second] == 0) {
            vis[it.second] = 1;
            dfs(it.first);
        }
    }
    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;
        g[x].push_back({y, i});
        g[y].push_back({x, 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 12032 KB Output is correct
2 Correct 12 ms 12160 KB Output is correct
3 Correct 17 ms 12160 KB Output is correct
4 Correct 13 ms 12288 KB Output is correct
5 Correct 12 ms 12160 KB Output is correct
6 Correct 15 ms 12416 KB Output is correct
7 Correct 17 ms 13184 KB Output is correct
8 Correct 14 ms 12288 KB Output is correct
9 Correct 44 ms 18208 KB Output is correct
10 Correct 13 ms 12288 KB Output is correct
11 Correct 14 ms 12288 KB Output is correct
12 Correct 51 ms 18548 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 12032 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 13 ms 12148 KB Output is correct
4 Correct 14 ms 12288 KB Output is correct
5 Correct 13 ms 12160 KB Output is correct
6 Correct 13 ms 12416 KB Output is correct
7 Correct 17 ms 13160 KB Output is correct
8 Correct 16 ms 12264 KB Output is correct
9 Correct 48 ms 18172 KB Output is correct
10 Correct 14 ms 12288 KB Output is correct
11 Correct 15 ms 12288 KB Output is correct
12 Correct 58 ms 18524 KB Output is correct
13 Correct 91 ms 19952 KB Output is correct
14 Correct 85 ms 18032 KB Output is correct
15 Correct 77 ms 19280 KB Output is correct
16 Correct 82 ms 19952 KB Output is correct
17 Correct 87 ms 16376 KB Output is correct
18 Correct 84 ms 18648 KB Output is correct

Subtask #3
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 12032 KB Output is correct
2 Correct 13 ms 12032 KB Output is correct
3 Correct 13 ms 12032 KB Output is correct
4 Correct 12 ms 12288 KB Output is correct
5 Correct 15 ms 12160 KB Output is correct
6 Correct 12 ms 12416 KB Output is correct
7 Correct 17 ms 13184 KB Output is correct
8 Correct 13 ms 12288 KB Output is correct
9 Correct 45 ms 18180 KB Output is correct
10 Correct 14 ms 12272 KB Output is correct
11 Correct 14 ms 12288 KB Output is correct
12 Correct 59 ms 18652 KB Output is correct
13 Correct 87 ms 19928 KB Output is correct
14 Correct 89 ms 18100 KB Output is correct
15 Correct 81 ms 19280 KB Output is correct
16 Correct 85 ms 19956 KB Output is correct
17 Correct 79 ms 16372 KB Output is correct
18 Correct 96 ms 18672 KB Output is correct
19 Correct 487 ms 51496 KB Output is correct
20 Correct 451 ms 42084 KB Output is correct
21 Correct 447 ms 47980 KB Output is correct
22 Execution timed out 516 ms 51420 KB Time limit exceeded
23 Halted 0 ms 0 KB -