oj.uz

답안 #472025

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
472025 2021-09-12T12:44:12 Z hidden1 어르신 집배원 (BOI14_postmen) C++14
100 / 100
 478 ms 42116 KB 
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "

const int MAX_N = 5e5 + 10;
vector<pair<int, int> > g[MAX_N];
bool used[MAX_N];
int n, m;
vector<int> ans;
int cnt[MAX_N];
bool in[MAX_N];

void dfs(int x) {
    stack<int> st;
    st.push(x);
    while(!st.empty()) {
        auto curr = st.top();
        int got = -1;
        for(; cnt[curr] < g[curr].size();) {
            auto it = g[curr][cnt[curr] ++];
            if(used[it.second]) {continue;}
            used[it.second] = true;
            got = it.first;
            break;
        }
        if(got == -1) {
            ans.push_back(curr);
            st.pop();
        } else {
            st.push(got);
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    for(int i = 0; i < m; i ++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }
    for(int i = 1; i <= n; i ++) {
        if(cnt[i] != g[i].size()) {
            dfs(i);
        }
    }
    stack<int> st;
    for(auto it : ans) {
        if(in[it]) {
            cout << it << " ";
            while(st.top() != it) {
                cout << st.top() << " ";
                in[st.top()] = false;
                st.pop();
            }
            cout << endl;
        } else {
            st.push(it);
            in[it] = true;
        }
    }
    return 0;
}

Compilation message

postmen.cpp: In function 'void dfs(int)':
postmen.cpp:28:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for(; cnt[curr] < g[curr].size();) {
      |               ~~~~~~~~~~^~~~~~~~~~~~~~~~
postmen.cpp: In function 'int main()':
postmen.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         if(cnt[i] != g[i].size()) {
      |            ~~~~~~~^~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 11980 KB Output is correct
2 Correct 9 ms 11980 KB Output is correct
3 Correct 7 ms 11980 KB Output is correct
4 Correct 9 ms 12236 KB Output is correct
5 Correct 8 ms 12108 KB Output is correct
6 Correct 9 ms 12236 KB Output is correct
7 Correct 13 ms 12848 KB Output is correct
8 Correct 8 ms 12108 KB Output is correct
9 Correct 46 ms 15640 KB Output is correct
10 Correct 9 ms 12236 KB Output is correct
11 Correct 8 ms 12236 KB Output is correct
12 Correct 48 ms 15900 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Correct 8 ms 12072 KB Output is correct
3 Correct 7 ms 12072 KB Output is correct
4 Correct 9 ms 12208 KB Output is correct
5 Correct 8 ms 12108 KB Output is correct
6 Correct 10 ms 12236 KB Output is correct
7 Correct 12 ms 12876 KB Output is correct
8 Correct 8 ms 12108 KB Output is correct
9 Correct 41 ms 15564 KB Output is correct
10 Correct 9 ms 12236 KB Output is correct
11 Correct 9 ms 12208 KB Output is correct
12 Correct 47 ms 15976 KB Output is correct
13 Correct 66 ms 17552 KB Output is correct
14 Correct 72 ms 16956 KB Output is correct
15 Correct 56 ms 17128 KB Output is correct
16 Correct 70 ms 17636 KB Output is correct
17 Correct 64 ms 16684 KB Output is correct
18 Correct 85 ms 17148 KB Output is correct

Subtask #3
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11980 KB Output is correct
2 Correct 7 ms 11980 KB Output is correct
3 Correct 7 ms 11980 KB Output is correct
4 Correct 9 ms 12236 KB Output is correct
5 Correct 9 ms 12036 KB Output is correct
6 Correct 10 ms 12236 KB Output is correct
7 Correct 13 ms 12852 KB Output is correct
8 Correct 8 ms 12092 KB Output is correct
9 Correct 47 ms 15524 KB Output is correct
10 Correct 9 ms 12236 KB Output is correct
11 Correct 9 ms 12152 KB Output is correct
12 Correct 45 ms 15936 KB Output is correct
13 Correct 63 ms 17584 KB Output is correct
14 Correct 64 ms 16852 KB Output is correct
15 Correct 58 ms 17228 KB Output is correct
16 Correct 63 ms 17600 KB Output is correct
17 Correct 69 ms 16740 KB Output is correct
18 Correct 71 ms 17180 KB Output is correct
19 Correct 434 ms 38516 KB Output is correct
20 Correct 411 ms 35568 KB Output is correct
21 Correct 381 ms 36392 KB Output is correct
22 Correct 445 ms 38680 KB Output is correct
23 Correct 180 ms 27132 KB Output is correct
24 Correct 478 ms 33968 KB Output is correct
25 Correct 454 ms 42116 KB Output is correct