oj.uz

Submission #882958

# Submission time Handle Problem Language Result Execution time Memory
882958 2023-12-04T09:12:05 Z Do_you_copy Senior Postmen (BOI14_postmen) C++17
100 / 100
 386 ms 65196 KB 
//Then
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
    
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 1;
//const int Mod = 1e9 + 7;
//const int inf =
int n, m;
    
struct TEdge{
    int u, v;
    bool del;
};
vector <TEdge> e;
vector <int> adj[maxN];
void add_edge(int u, int v){
    adj[u].pb(e.size());
    adj[v].pb(e.size());
    e.pb({u, v, 0});
}
vector <int> euler(int s){
    vector <int> res;
    vector <int> S(1, s);
    while (!S.empty()){
        int u = S.back();
        while (!adj[u].empty() && e[adj[u].back()].del) adj[u].pop_back();
        if (!adj[u].empty()){
            auto &i = e[adj[u].back()];
            S.pb(i.u ^ i.v ^ u);
            i.del = 1;
            adj[u].pop_back();
        }
        else{
            res.pb(u);
            S.pop_back();
        }
    }
    return res;
}

int visited[maxN];
void Init(){
    cin >> n >> m;
    for (int i = 1; i <= m; ++i){
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
    }
    vector <int> eulertour = euler(1);
    vector <int> ans;
    for (int u: eulertour){
        if (visited[u]){
            int v;
            do{
                v = ans.back();
                visited[v] = 0;
                cout << v << " ";
                ans.pop_back();
            } while (v != u);
            cout << "\n";
        }
        ans.pb(u);
        visited[u] = 1;
    }
}
    
#define debug
#define taskname "test"
signed main(){
    faster
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    int tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
    if (fopen("timeout.txt", "r")){
        ofstream timeout("timeout.txt");
        timeout << signed(double(clock()) / CLOCKS_PER_SEC * 1000);
        timeout.close();
        #ifndef debug
        cerr << "Time elapsed: " << signed(double(clock()) / CLOCKS_PER_SEC * 1000) << "ms\n";
        #endif // debug
    }
}

Compilation message

postmen.cpp: In function 'int main()':
postmen.cpp:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
postmen.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25436 KB Output is correct
2 Correct 6 ms 25436 KB Output is correct
3 Correct 5 ms 25564 KB Output is correct
4 Correct 8 ms 25692 KB Output is correct
5 Correct 6 ms 25692 KB Output is correct
6 Correct 6 ms 25692 KB Output is correct
7 Correct 9 ms 26200 KB Output is correct
8 Correct 6 ms 25692 KB Output is correct
9 Correct 26 ms 30176 KB Output is correct
10 Correct 7 ms 25692 KB Output is correct
11 Correct 6 ms 25692 KB Output is correct
12 Correct 29 ms 30788 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25688 KB Output is correct
2 Correct 5 ms 25436 KB Output is correct
3 Correct 6 ms 25436 KB Output is correct
4 Correct 7 ms 25692 KB Output is correct
5 Correct 6 ms 25692 KB Output is correct
6 Correct 7 ms 25820 KB Output is correct
7 Correct 9 ms 26200 KB Output is correct
8 Correct 6 ms 25692 KB Output is correct
9 Correct 27 ms 30148 KB Output is correct
10 Correct 7 ms 25688 KB Output is correct
11 Correct 6 ms 25692 KB Output is correct
12 Correct 32 ms 30724 KB Output is correct
13 Correct 43 ms 33268 KB Output is correct
14 Correct 41 ms 32264 KB Output is correct
15 Correct 38 ms 32008 KB Output is correct
16 Correct 43 ms 33292 KB Output is correct
17 Correct 41 ms 32000 KB Output is correct
18 Correct 41 ms 32268 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25432 KB Output is correct
2 Correct 6 ms 25436 KB Output is correct
3 Correct 5 ms 25632 KB Output is correct
4 Correct 6 ms 25692 KB Output is correct
5 Correct 8 ms 25692 KB Output is correct
6 Correct 7 ms 25688 KB Output is correct
7 Correct 9 ms 26200 KB Output is correct
8 Correct 6 ms 25692 KB Output is correct
9 Correct 27 ms 30220 KB Output is correct
10 Correct 7 ms 25688 KB Output is correct
11 Correct 6 ms 25692 KB Output is correct
12 Correct 32 ms 30728 KB Output is correct
13 Correct 47 ms 33284 KB Output is correct
14 Correct 39 ms 32308 KB Output is correct
15 Correct 40 ms 31884 KB Output is correct
16 Correct 41 ms 33376 KB Output is correct
17 Correct 41 ms 31748 KB Output is correct
18 Correct 42 ms 32260 KB Output is correct
19 Correct 373 ms 64972 KB Output is correct
20 Correct 308 ms 59892 KB Output is correct
21 Correct 281 ms 58112 KB Output is correct
22 Correct 386 ms 65196 KB Output is correct
23 Correct 114 ms 47504 KB Output is correct
24 Correct 313 ms 58044 KB Output is correct
25 Correct 285 ms 59896 KB Output is correct