oj.uz

Submission #704199

# Submission time Handle Problem Language Result Execution time Memory
704199 2023-03-01T22:53:22 Z boyliguanhan Senior Postmen (BOI14_postmen) C++17
100 / 100
 343 ms 75060 KB 
#include<bits/stdc++.h>
#pragma GCC optimize(2)
//#define getchar_unlocked _getchar_nolock
using namespace std;
vector<pair<int, int>> adj[500100];
bitset<500100> removed;
int cnt[500100];
stack<int> sol;
int read(){
    int res = 0, c = getchar_unlocked();
    while(c < '0' || c > '9')
        c = getchar_unlocked();
    while(isdigit(c))
        res = res*10+c - 48, c = getchar_unlocked();
    return res;
}
void reverse(){
    stack<int> temp;
    while(sol.size())
        temp.push(sol.top()), sol.pop();
    sol = temp;
}
void print(){
    stack<int> now;
    bitset<500100> appeared;
    while(sol.size()){
        if(appeared[sol.top()]){
            printf("%d", sol.top());
            while(now.top()!=sol.top())
                printf(" %d", now.top()), appeared[now.top()] = 0, now.pop();
            printf("\n");
        } else {
            appeared[sol.top()] = 1;
            now.push(sol.top());
        }
        sol.pop();
    }
}
void dfs(int n){
    for(int i = cnt[n]; i < adj[n].size(); i = cnt[n]){
        cnt[n] = i+1;
        if(!removed[adj[n][i].second])
            removed[adj[n][i].second] = 1, dfs(adj[n][i].first);
    }
    sol.push(n);
}
int main(){
    int n = read(), m = read();
    for(int i = 0; i < m; i++) {
        int a = read(), b = read();
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
    }
    dfs(1);
    reverse();
    print();
    return 0;
}

Compilation message

postmen.cpp: In function 'void dfs(int)':
postmen.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i = cnt[n]; i < adj[n].size(); i = cnt[n]){
      |                         ~~^~~~~~~~~~~~~~~
postmen.cpp: In function 'int main()':
postmen.cpp:48:9: warning: unused variable 'n' [-Wunused-variable]
   48 |     int n = read(), m = read();
      |         ^

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12116 KB Output is correct
2 Correct 8 ms 12004 KB Output is correct
3 Correct 6 ms 12116 KB Output is correct
4 Correct 7 ms 12244 KB Output is correct
5 Correct 7 ms 12092 KB Output is correct
6 Correct 7 ms 12500 KB Output is correct
7 Correct 9 ms 13572 KB Output is correct
8 Correct 7 ms 12244 KB Output is correct
9 Correct 27 ms 21332 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 7 ms 12244 KB Output is correct
12 Correct 28 ms 21580 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11988 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct
3 Correct 6 ms 12116 KB Output is correct
4 Correct 8 ms 12244 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 7 ms 12500 KB Output is correct
7 Correct 9 ms 13524 KB Output is correct
8 Correct 7 ms 12276 KB Output is correct
9 Correct 28 ms 21296 KB Output is correct
10 Correct 7 ms 12244 KB Output is correct
11 Correct 7 ms 12244 KB Output is correct
12 Correct 28 ms 21684 KB Output is correct
13 Correct 40 ms 23244 KB Output is correct
14 Correct 42 ms 19704 KB Output is correct
15 Correct 38 ms 22356 KB Output is correct
16 Correct 46 ms 23248 KB Output is correct
17 Correct 43 ms 17136 KB Output is correct
18 Correct 39 ms 21204 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 6 ms 12080 KB Output is correct
3 Correct 6 ms 12116 KB Output is correct
4 Correct 7 ms 12244 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 8 ms 12500 KB Output is correct
7 Correct 9 ms 13524 KB Output is correct
8 Correct 7 ms 12244 KB Output is correct
9 Correct 25 ms 21352 KB Output is correct
10 Correct 7 ms 12244 KB Output is correct
11 Correct 7 ms 12244 KB Output is correct
12 Correct 29 ms 21712 KB Output is correct
13 Correct 41 ms 23236 KB Output is correct
14 Correct 39 ms 19700 KB Output is correct
15 Correct 39 ms 22456 KB Output is correct
16 Correct 41 ms 23156 KB Output is correct
17 Correct 44 ms 17200 KB Output is correct
18 Correct 40 ms 21192 KB Output is correct
19 Correct 302 ms 68516 KB Output is correct
20 Correct 269 ms 51036 KB Output is correct
21 Correct 266 ms 64432 KB Output is correct
22 Correct 343 ms 75060 KB Output is correct
23 Correct 114 ms 61180 KB Output is correct
24 Correct 308 ms 43596 KB Output is correct
25 Correct 303 ms 65148 KB Output is correct