oj.uz

Submission #484438

# Submission time Handle Problem Language Result Execution time Memory
484438 2021-11-03T11:41:07 Z ACmachine Senior Postmen (BOI14_postmen) C++17
100 / 100
 370 ms 43772 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;

#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)

const double EPS = 1e-9;
const int MOD = 1e9+7;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};

void DBG(){cout << "]" << endl;}
template<typename T, typename ...U> void DBG(const T& head, const U... args){ cout << head << "; "; DBG(args...); }
#define dbg(...) cout << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__);
#define chk() cout << "Check at line(" << __LINE__ << ") hit." << endl;

template<class T, unsigned int U>
ostream& operator<<(ostream& out, const array<T, U> &v){out << "[";  REP(i, U) out << v[i] << ", ";  out << "]"; return out;}
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}

template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// g[x] = {y, edge_id}
// m = number of edges in graph;
vector<int> find_eulerian_path(const vector<vector<array<int, 2>>> &g, int m, int s){
    vector<bool> visited(m, false);
    vector<int> ptr(g.size(), 0);
    vector<int> stk, tour;
    stk.push_back(s);
    while(!stk.empty()){
        bool found = false;
        int v = stk.back();
        while(ptr[v] < g[v].size()){
            int id = g[v][ptr[v]][1];
            if(visited[id]){
                ptr[v]++; continue;
            }
            stk.push_back(g[v][ptr[v]][0]);
            visited[id] = true; ptr[v]++;
            found = true;
            break;
        }
        if(!found){
            tour.push_back(v);
            stk.pop_back();
        }
    }
    reverse(all(tour));
    return tour;
}

int main(){
 	ios_base::sync_with_stdio(false);
 	cin.tie(NULL); cout.tie(NULL);
 	int n, m;
 	cin >> n >> m;
 	vector<vector<array<int, 2>>> g(n);
    REP(i, m){
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].pb({v, i});
        g[v].pb({u, i});
    }
    vector<int> tour_res = find_eulerian_path(g, m, 0);
    vector<bool> is_on_stack(n, false);
    vector<int> st;
    vector<vector<int>> ans;
    REP(i, tour_res.size()){
        if(is_on_stack[tour_res[i]]){
            while(st.back() != tour_res[i]){
                is_on_stack[st.back()] = false;
                cout << st.back() + 1 << " ";
                st.pop_back();

            }
            cout << st.back() + 1 << "\n";
        }
        else{
            st.push_back(tour_res[i]);
            is_on_stack[tour_res[i]] = true;
        }
    }
    return 0;
}

Compilation message

postmen.cpp: In function 'std::vector<int> find_eulerian_path(const std::vector<std::vector<std::array<int, 2> > >&, int, int)':
postmen.cpp:69:22: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         while(ptr[v] < g[v].size()){
postmen.cpp: In function 'int main()':
postmen.cpp:19:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
      |                                        ^
postmen.cpp:21:18: note: in expansion of macro 'FOR'
   21 | #define REP(i,b) FOR(i,0,b,1)
      |                  ^~~
postmen.cpp:105:5: note: in expansion of macro 'REP'
  105 |     REP(i, tour_res.size()){
      |     ^~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 452 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 4 ms 1100 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 25 ms 4152 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 33 ms 4648 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 5 ms 1136 KB Output is correct
8 Correct 1 ms 452 KB Output is correct
9 Correct 27 ms 4164 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 32 ms 4660 KB Output is correct
13 Correct 45 ms 8752 KB Output is correct
14 Correct 41 ms 7484 KB Output is correct
15 Correct 38 ms 7352 KB Output is correct
16 Correct 42 ms 8772 KB Output is correct
17 Correct 40 ms 6832 KB Output is correct
18 Correct 46 ms 7448 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 7 ms 1100 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 26 ms 4240 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 29 ms 4608 KB Output is correct
13 Correct 62 ms 8752 KB Output is correct
14 Correct 40 ms 7504 KB Output is correct
15 Correct 36 ms 7352 KB Output is correct
16 Correct 47 ms 8808 KB Output is correct
17 Correct 40 ms 6836 KB Output is correct
18 Correct 44 ms 7364 KB Output is correct
19 Correct 370 ms 43772 KB Output is correct
20 Correct 312 ms 37400 KB Output is correct
21 Correct 298 ms 36012 KB Output is correct
22 Correct 352 ms 43744 KB Output is correct
23 Correct 129 ms 17952 KB Output is correct
24 Correct 346 ms 33456 KB Output is correct
25 Correct 344 ms 36212 KB Output is correct