oj.uz

Submission #994006

# Submission time Handle Problem Language Result Execution time Memory
994006 2024-06-07T01:41:02 Z NoLove Senior Postmen (BOI14_postmen) C++14
100 / 100
 261 ms 110400 KB 
/**
 *    author : Lăng Trọng Đạt
 *    created: 07-06-2024 
**/
#include <bits/stdc++.h>
using namespace std;
#ifndef LANG_DAT
#define db(...) ;
#endif // LANG_DAT
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define all(v) (v).begin(), (v).end()
using pii = pair<int, int>;
using vi = vector<int>;
#define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
void mx(int& a, int b) { if (b > a) a = b; }
void mi(int& a, int b) { if (b < a) a = b; }
#define si(x) (int)(x.size())
const int INF = 1e18;
const int MOD = 1e9 + 7;
 
const int MAXN = 1e6 + 5;
vector<pii> adj[MAXN];
 
int n, m, a, b;
vector<vi> ans;
bitset<MAXN> in_q, use;
vi path, tour;
void dfs(int v) {
    if (in_q[v]) {
        ans.pb({v});
        in_q[v] = false;
        while (path.back() != v) {
            ans.back().pb({path.back()});
            in_q[path.back()] = 0;
            path.pop_back();
        }
        path.pop_back();
    } 
    while (si(adj[v])) {
        auto[u, id] = adj[v].back();
        adj[v].pop_back();
        if (use[id]) continue;
        use[id] = true;
        if (!in_q[v]) {
            path.pb(v);
            in_q[v] = 1;
        }
        dfs(u);
    }
}
int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    if (fopen("hi.inp", "r")) {
        freopen("hi.txt", "r", stdin);
       freopen("hi.out", "w", stdout);
    } 
 
    cin >> n >> m;
    FOR(i, 1, m) {
        cin >> a >> b;
        adj[a].pb({b, i});
        adj[b].pb({a, i});
    }
    dfs(1);
    int cnt = 0;
    for (auto v : ans) {
        for (int i : v) {
            cout << i << " ";
        }
        cout << "\n";
    }
}

Compilation message

postmen.cpp:21:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   21 | const int INF = 1e18;
      |                 ^~~~
postmen.cpp: In function 'void dfs(int)':
postmen.cpp:43:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |         auto[u, id] = adj[v].back();
      |             ^
postmen.cpp: In function 'int32_t main()':
postmen.cpp:17:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
      |                               ^
postmen.cpp:62:5: note: in expansion of macro 'FOR'
   62 |     FOR(i, 1, m) {
      |     ^~~
postmen.cpp:68:9: warning: unused variable 'cnt' [-Wunused-variable]
   68 |     int cnt = 0;
      |         ^~~
postmen.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         freopen("hi.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
postmen.cpp:58:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |        freopen("hi.out", "w", stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23896 KB Output is correct
2 Correct 4 ms 23900 KB Output is correct
3 Correct 4 ms 23900 KB Output is correct
4 Correct 5 ms 24412 KB Output is correct
5 Correct 4 ms 24160 KB Output is correct
6 Correct 5 ms 24640 KB Output is correct
7 Correct 8 ms 26336 KB Output is correct
8 Correct 5 ms 24160 KB Output is correct
9 Correct 30 ms 38488 KB Output is correct
10 Correct 5 ms 24160 KB Output is correct
11 Correct 5 ms 24156 KB Output is correct
12 Correct 38 ms 38996 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23900 KB Output is correct
2 Correct 4 ms 23896 KB Output is correct
3 Correct 4 ms 23900 KB Output is correct
4 Correct 5 ms 24412 KB Output is correct
5 Correct 4 ms 24200 KB Output is correct
6 Correct 5 ms 24668 KB Output is correct
7 Correct 8 ms 26204 KB Output is correct
8 Correct 5 ms 24268 KB Output is correct
9 Correct 32 ms 38484 KB Output is correct
10 Correct 5 ms 24408 KB Output is correct
11 Correct 5 ms 24156 KB Output is correct
12 Correct 34 ms 38996 KB Output is correct
13 Correct 45 ms 40984 KB Output is correct
14 Correct 46 ms 35300 KB Output is correct
15 Correct 42 ms 40672 KB Output is correct
16 Correct 44 ms 41092 KB Output is correct
17 Correct 37 ms 31328 KB Output is correct
18 Correct 41 ms 38408 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23900 KB Output is correct
2 Correct 4 ms 23992 KB Output is correct
3 Correct 4 ms 23896 KB Output is correct
4 Correct 5 ms 24408 KB Output is correct
5 Correct 5 ms 24156 KB Output is correct
6 Correct 5 ms 24668 KB Output is correct
7 Correct 8 ms 26204 KB Output is correct
8 Correct 6 ms 24156 KB Output is correct
9 Correct 30 ms 38488 KB Output is correct
10 Correct 5 ms 24152 KB Output is correct
11 Correct 5 ms 24156 KB Output is correct
12 Correct 35 ms 38932 KB Output is correct
13 Correct 41 ms 41040 KB Output is correct
14 Correct 39 ms 35272 KB Output is correct
15 Correct 40 ms 40644 KB Output is correct
16 Correct 45 ms 41036 KB Output is correct
17 Correct 40 ms 31252 KB Output is correct
18 Correct 39 ms 38408 KB Output is correct
19 Correct 261 ms 110400 KB Output is correct
20 Correct 223 ms 82108 KB Output is correct
21 Correct 242 ms 109772 KB Output is correct
22 Correct 249 ms 110400 KB Output is correct
23 Correct 136 ms 95832 KB Output is correct
24 Correct 225 ms 62752 KB Output is correct
25 Correct 235 ms 97020 KB Output is correct