oj.uz

Submission #484440

# Submission time Handle Problem Language Result Execution time Memory
484440 2021-11-03T12:02:44 Z ACmachine Senior Postmen (BOI14_postmen) C++17
100 / 100
 403 ms 45288 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());


// returns -2 if doesn't exist, -1 if cycle, else possible starting vertex; doesn't check if connected
int check_eulerian_path(const vector<vector<array<int, 2>>> &g){

}
// g[x] = {y, edge_id}
// m = number of edges in graph;
// returns the edge_ids on the path
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<array<int, 2>> stk;
    vector<int> tour;
    stk.push_back({s, -1});
    while(!stk.empty()){
        bool found = false;
        int v = stk.back()[0];
        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], id});
            visited[id] = true; ptr[v]++;
            found = true;
            break;
        }
        if(!found){
            tour.push_back(stk.back()[1]);
            stk.pop_back();
        }
    }
    tour.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);
 	vector<array<int, 2>> edges;
    REP(i, m){
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].pb({v, i});
        g[v].pb({u, i});
        edges.pb({u, v});
    }
    vector<int> tour_tm = find_eulerian_path(g, m, 0);
    vector<int> tour_res; tour_res.pb(0);
    REP(i, tour_tm.size()){
        int id = tour_tm[i];
        auto e = edges[id];
        tour_res.pb(e[0] ^ e[1] ^ tour_res.back());
    }
    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 'int check_eulerian_path(const std::vector<std::vector<std::array<int, 2> > >&)':
postmen.cpp:63:1: warning: no return statement in function returning non-void [-Wreturn-type]
   63 | }
      | ^
postmen.cpp: In function 'std::vector<int> find_eulerian_path(const std::vector<std::vector<std::array<int, 2> > >&, int, int)':
postmen.cpp:76: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]
   76 |         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:113:5: note: in expansion of macro 'REP'
  113 |     REP(i, tour_tm.size()){
      |     ^~~
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:121:5: note: in expansion of macro 'REP'
  121 |     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 0 ms 204 KB Output is correct
3 Correct 0 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 588 KB Output is correct
7 Correct 7 ms 1116 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 29 ms 4860 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 34 ms 5224 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 0 ms 204 KB Output is correct
3 Correct 0 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 588 KB Output is correct
7 Correct 5 ms 1108 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 28 ms 4804 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 32 ms 5132 KB Output is correct
13 Correct 57 ms 9344 KB Output is correct
14 Correct 45 ms 8052 KB Output is correct
15 Correct 41 ms 7316 KB Output is correct
16 Correct 47 ms 9264 KB Output is correct
17 Correct 46 ms 7736 KB Output is correct
18 Correct 60 ms 7920 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 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 588 KB Output is correct
7 Correct 5 ms 1108 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 29 ms 4888 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 35 ms 5212 KB Output is correct
13 Correct 52 ms 9392 KB Output is correct
14 Correct 44 ms 8044 KB Output is correct
15 Correct 45 ms 7348 KB Output is correct
16 Correct 48 ms 9260 KB Output is correct
17 Correct 49 ms 7668 KB Output is correct
18 Correct 47 ms 7920 KB Output is correct
19 Correct 384 ms 45288 KB Output is correct
20 Correct 348 ms 38324 KB Output is correct
21 Correct 322 ms 35136 KB Output is correct
22 Correct 384 ms 45192 KB Output is correct
23 Correct 145 ms 21092 KB Output is correct
24 Correct 403 ms 36984 KB Output is correct
25 Correct 363 ms 38200 KB Output is correct