oj.uz

답안 #861261

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
861261 2023-10-15T18:16:49 Z qwusha 어르신 집배원 (BOI14_postmen) C++17
100 / 100
 349 ms 86768 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma gcc optimize("Ofast")
using namespace std;
typedef long long ll;
#define fi first
#define se second
typedef long double ld;
const ll inf = 1e9;
const ld eps = 1e-8;
vector<vector<int>> g;
vector<vector<int>> ans;
vector<bool> used;
vector<int> cur;
vector<int> stcur;
vector<int> res;

struct vert {
    int to;
    bool used;
};

vector<vert> ve;


void add_vert(int v, int u) {
    g[v].push_back(ve.size());
    ve.push_back({u, 0});
    g[u].push_back(ve.size());
    ve.push_back({v, 0});
}



void dfs(int v) {
    if (stcur[v] > 0) {
        res.clear();
        while(cur.back() != v) {
            stcur[cur.back()]--;
            res.push_back(cur.back());
            cur.pop_back();
        }
        stcur[cur.back()]--;
        res.push_back(cur.back());
        cur.pop_back();
        ans.push_back(res);
    }

    while (!g[v].empty()) {
        int e = g[v].back();
        g[v].pop_back();
        if (!ve[e].used) {
            cur.push_back(v);
            stcur[v]++;
            ve[e].used = 1;
            ve[(e ^ 1)].used = 1;
            dfs(ve[e].to);
        }
    }
}



signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    used.resize(n);
    g.resize(n);
    for (int i = 0; i < m; i++) {
        int v, u;
        cin >> v >> u;
        v--;
        u--;
        add_vert(v, u);
    }
    stcur.resize(n);
    dfs(0);
    for (auto s : ans) {
        for (auto el : s) {
            cout << el + 1 << ' ';
        }
        cout << '\n';
    }
}

Compilation message

postmen.cpp:4: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    4 | #pragma gcc optimize("Ofast")
      |

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 4 ms 1872 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 24 ms 9924 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 27 ms 10280 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 4 ms 1872 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 28 ms 10164 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 28 ms 10404 KB Output is correct
13 Correct 36 ms 16320 KB Output is correct
14 Correct 39 ms 11460 KB Output is correct
15 Correct 36 ms 15400 KB Output is correct
16 Correct 36 ms 16320 KB Output is correct
17 Correct 36 ms 9672 KB Output is correct
18 Correct 45 ms 13504 KB Output is correct

Subtask #3
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 4 ms 1872 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 25 ms 10188 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 28 ms 10444 KB Output is correct
13 Correct 59 ms 16320 KB Output is correct
14 Correct 38 ms 11468 KB Output is correct
15 Correct 41 ms 15560 KB Output is correct
16 Correct 37 ms 16328 KB Output is correct
17 Correct 38 ms 9664 KB Output is correct
18 Correct 47 ms 13504 KB Output is correct
19 Correct 334 ms 80188 KB Output is correct
20 Correct 315 ms 56244 KB Output is correct
21 Correct 297 ms 80168 KB Output is correct
22 Correct 349 ms 86768 KB Output is correct
23 Correct 130 ms 51988 KB Output is correct
24 Correct 342 ms 52872 KB Output is correct
25 Correct 317 ms 72248 KB Output is correct