oj.uz

답안 #980658

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
980658 2024-05-12T09:50:45 Z Zicrus 어르신 집배원 (BOI14_postmen) C++17
55 / 100
 123 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll n, m, u, v;
vector<queue<pair<ll, ll>>> adj;
vector<ll> res;

vector<bool> sus;

void euler(ll s) {
    while (!adj[s].empty()) {
        ll e = adj[s].front().first;
        ll i = adj[s].front().second;
        adj[s].pop();
        if (!sus[i]) { sus[i] = true; euler(e); }
        sus[i] = true;
    }
    res.push_back(s);
}

int main() {
    cin >> n >> m;
    adj.resize(n);
    sus.resize(m);
    vector<ll> deg(n);
    ll g = 0;
    for (ll i = 0; i < m; i++) {
        cin >> u >> v;
        adj[u-1].push({v-1, g});
        adj[v-1].push({u-1, g++});
    }

    euler(0);
    reverse(res.begin(), res.end());
    vector<ll> vst(n, -1);
    vector<ll> nxt(n, -1);
    for (ll i = 0; i < res.size(); i++) {
        ll node = res[i];
        if (vst[node] == -1) {
            vst[node] = i;
            nxt[node] = res[i+1];
        }
        else {
            ll nd = res[vst[node]];
            do {
                cout << nd+1 << ' ';
                vst[nd] = -1;
                nd = nxt[nd];
            } while (nd != node);
            cout << '\n';
            nxt[node] = res[i+1];
            vst[node] = i;
        }
    }
}

Compilation message

postmen.cpp: In function 'int main()':
postmen.cpp:39:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (ll i = 0; i < res.size(); i++) {
      |                    ~~^~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 3 ms 1884 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 7 ms 2140 KB Output is correct
8 Correct 2 ms 1884 KB Output is correct
9 Correct 54 ms 12116 KB Output is correct
10 Correct 2 ms 1880 KB Output is correct
11 Correct 2 ms 2132 KB Output is correct
12 Correct 50 ms 13032 KB Output is correct

Subtask #2
17.0 / 17.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 3 ms 2292 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 856 KB Output is correct
7 Correct 7 ms 2140 KB Output is correct
8 Correct 2 ms 1884 KB Output is correct
9 Correct 44 ms 11856 KB Output is correct
10 Correct 2 ms 1884 KB Output is correct
11 Correct 2 ms 1884 KB Output is correct
12 Correct 56 ms 13136 KB Output is correct
13 Correct 105 ms 79304 KB Output is correct
14 Correct 100 ms 58032 KB Output is correct
15 Correct 100 ms 56400 KB Output is correct
16 Correct 112 ms 79304 KB Output is correct
17 Correct 123 ms 49096 KB Output is correct
18 Correct 106 ms 59848 KB Output is correct

Subtask #3
0 / 45.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 536 KB Output is correct
4 Correct 2 ms 2136 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 7 ms 2136 KB Output is correct
8 Correct 2 ms 1884 KB Output is correct
9 Correct 44 ms 11860 KB Output is correct
10 Correct 2 ms 1884 KB Output is correct
11 Correct 2 ms 1884 KB Output is correct
12 Correct 48 ms 13140 KB Output is correct
13 Correct 109 ms 79412 KB Output is correct
14 Correct 99 ms 58052 KB Output is correct
15 Correct 96 ms 56396 KB Output is correct
16 Correct 121 ms 79304 KB Output is correct
17 Correct 113 ms 49092 KB Output is correct
18 Correct 119 ms 59812 KB Output is correct
19 Runtime error 112 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -