oj.uz

Submission #704196

# Submission time Handle Problem Language Result Execution time Memory
704196 2023-03-01T22:49:49 Z boyliguanhan Senior Postmen (BOI14_postmen) C++17
38 / 100
 500 ms 24816 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 + 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++)
      |                         ~~^~~~~~~~~~~~~~~
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 6 ms 12116 KB Output is correct
2 Correct 7 ms 12032 KB Output is correct
3 Correct 6 ms 12088 KB Output is correct
4 Correct 9 ms 12372 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 8 ms 12500 KB Output is correct
7 Correct 14 ms 13840 KB Output is correct
8 Correct 7 ms 12244 KB Output is correct
9 Correct 64 ms 22860 KB Output is correct
10 Correct 8 ms 12244 KB Output is correct
11 Correct 7 ms 12244 KB Output is correct
12 Correct 39 ms 23248 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12048 KB Output is correct
2 Correct 6 ms 12116 KB Output is correct
3 Correct 6 ms 12116 KB Output is correct
4 Correct 10 ms 12372 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 9 ms 12500 KB Output is correct
7 Correct 13 ms 13844 KB Output is correct
8 Correct 7 ms 12244 KB Output is correct
9 Correct 68 ms 22888 KB Output is correct
10 Correct 7 ms 12244 KB Output is correct
11 Correct 7 ms 12244 KB Output is correct
12 Correct 43 ms 23248 KB Output is correct
13 Correct 46 ms 24816 KB Output is correct
14 Correct 36 ms 20428 KB Output is correct
15 Execution timed out 1083 ms 23036 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 6 ms 12116 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Correct 11 ms 12372 KB Output is correct
5 Correct 6 ms 12184 KB Output is correct
6 Correct 8 ms 12500 KB Output is correct
7 Correct 12 ms 13780 KB Output is correct
8 Correct 6 ms 12236 KB Output is correct
9 Correct 68 ms 22824 KB Output is correct
10 Correct 7 ms 12244 KB Output is correct
11 Correct 7 ms 12244 KB Output is correct
12 Correct 44 ms 23144 KB Output is correct
13 Correct 42 ms 24788 KB Output is correct
14 Correct 45 ms 20428 KB Output is correct
15 Execution timed out 1085 ms 23128 KB Time limit exceeded
16 Halted 0 ms 0 KB -