oj.uz

Submission #704194

# Submission time Handle Problem Language Result Execution time Memory
704194 2023-03-01T22:48:27 Z boyliguanhan Senior Postmen (BOI14_postmen) C++17
38 / 100
 500 ms 23244 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++)
        if(!removed[adj[n][i].second])
            removed[adj[n][i].second] = 1, cnt[n] = i, 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++)
      |                         ~~^~~~~~~~~~~~~~~
postmen.cpp: In function 'int main()':
postmen.cpp:46:9: warning: unused variable 'n' [-Wunused-variable]
   46 |     int n = read(), m = read();
      |         ^

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 8 ms 12116 KB Output is correct
3 Correct 8 ms 12116 KB Output is correct
4 Correct 10 ms 12244 KB Output is correct
5 Correct 8 ms 12116 KB Output is correct
6 Correct 7 ms 12500 KB Output is correct
7 Correct 11 ms 13604 KB Output is correct
8 Correct 6 ms 12244 KB Output is correct
9 Correct 70 ms 21280 KB Output is correct
10 Correct 7 ms 12244 KB Output is correct
11 Correct 7 ms 12244 KB Output is correct
12 Correct 47 ms 21632 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct
3 Correct 7 ms 12060 KB Output is correct
4 Correct 9 ms 12244 KB Output is correct
5 Correct 6 ms 12172 KB Output is correct
6 Correct 7 ms 12488 KB Output is correct
7 Correct 11 ms 13592 KB Output is correct
8 Correct 7 ms 12244 KB Output is correct
9 Correct 72 ms 21220 KB Output is correct
10 Correct 7 ms 12244 KB Output is correct
11 Correct 6 ms 12244 KB Output is correct
12 Correct 45 ms 21688 KB Output is correct
13 Correct 42 ms 23168 KB Output is correct
14 Correct 38 ms 19660 KB Output is correct
15 Execution timed out 1091 ms 21492 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12048 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct
3 Correct 6 ms 12040 KB Output is correct
4 Correct 10 ms 12368 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 8 ms 12500 KB Output is correct
7 Correct 11 ms 13524 KB Output is correct
8 Correct 7 ms 12172 KB Output is correct
9 Correct 65 ms 21220 KB Output is correct
10 Correct 8 ms 12244 KB Output is correct
11 Correct 8 ms 12244 KB Output is correct
12 Correct 39 ms 21628 KB Output is correct
13 Correct 42 ms 23244 KB Output is correct
14 Correct 39 ms 19688 KB Output is correct
15 Execution timed out 1084 ms 21552 KB Time limit exceeded
16 Halted 0 ms 0 KB -