oj.uz

Submission #964241

# Submission time Handle Problem Language Result Execution time Memory
964241 2024-04-16T13:22:24 Z GrindMachine Senior Postmen (BOI14_postmen) C++17
55 / 100
 500 ms 135720 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
https://github.com/dolphingarlic/CompetitiveProgramming/blob/master/Baltic/Baltic%2014-postmen.cpp
https://codeforces.com/blog/entry/49035 (algorithm to find euler circuit)

*/

const int MOD = 1e9 + 7;
const int N = 5e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

set<pii> adj[N];
vector<int> ord;
 
void dfs1(int u){
    while(!adj[u].empty()){
        auto [v,id] = *adj[u].begin();
        adj[u].erase(adj[u].begin());
        adj[v].erase({u,id});
        dfs1(v);
    }
 
    ord.pb(u);
}
 
void solve(int test_case)
{
    int n,m; cin >> n >> m;
    rep1(i,m){
        int u,v; cin >> u >> v;
        adj[u].insert({v,i}), adj[v].insert({u,i});
    }
 
    dfs1(1);
    ord.pop_back();

    vector<vector<int>> ans;
    vector<int> curr;
    vector<bool> there(n+5);

    trav(u,ord){
        if(!there[u]){
            curr.pb(u);
            there[u] = 1;
            conts;
        }

        vector<int> cyc;
        cyc.pb(u);

        while(curr.back() != u){
            cyc.pb(curr.back());
            there[curr.back()] = 0;
            curr.pop_back();
        }

        reverse(all(cyc));
        ans.pb(cyc);
    }

    ans.pb(curr);
    
    trav(cyc,ans){
        trav(u,cyc){
            cout << u << " ";
        }

        cout << endl;
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23900 KB Output is correct
2 Correct 6 ms 23900 KB Output is correct
3 Correct 5 ms 24056 KB Output is correct
4 Correct 8 ms 24464 KB Output is correct
5 Correct 6 ms 24156 KB Output is correct
6 Correct 8 ms 24664 KB Output is correct
7 Correct 17 ms 27128 KB Output is correct
8 Correct 6 ms 24156 KB Output is correct
9 Correct 121 ms 45252 KB Output is correct
10 Correct 7 ms 24412 KB Output is correct
11 Correct 6 ms 24156 KB Output is correct
12 Correct 86 ms 45396 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23944 KB Output is correct
2 Correct 5 ms 23896 KB Output is correct
3 Correct 6 ms 23900 KB Output is correct
4 Correct 9 ms 24412 KB Output is correct
5 Correct 6 ms 24152 KB Output is correct
6 Correct 9 ms 24884 KB Output is correct
7 Correct 15 ms 26972 KB Output is correct
8 Correct 7 ms 24156 KB Output is correct
9 Correct 95 ms 45140 KB Output is correct
10 Correct 7 ms 24412 KB Output is correct
11 Correct 8 ms 24156 KB Output is correct
12 Correct 83 ms 45416 KB Output is correct
13 Correct 65 ms 45904 KB Output is correct
14 Correct 82 ms 45924 KB Output is correct
15 Correct 76 ms 45524 KB Output is correct
16 Correct 66 ms 45908 KB Output is correct
17 Correct 77 ms 45832 KB Output is correct
18 Correct 66 ms 38248 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23896 KB Output is correct
2 Correct 6 ms 23900 KB Output is correct
3 Correct 5 ms 23900 KB Output is correct
4 Correct 9 ms 24412 KB Output is correct
5 Correct 6 ms 24152 KB Output is correct
6 Correct 8 ms 24664 KB Output is correct
7 Correct 15 ms 26972 KB Output is correct
8 Correct 6 ms 24156 KB Output is correct
9 Correct 95 ms 45264 KB Output is correct
10 Correct 7 ms 24408 KB Output is correct
11 Correct 7 ms 24156 KB Output is correct
12 Correct 85 ms 45524 KB Output is correct
13 Correct 82 ms 45904 KB Output is correct
14 Correct 76 ms 46012 KB Output is correct
15 Correct 90 ms 45628 KB Output is correct
16 Correct 75 ms 45908 KB Output is correct
17 Correct 84 ms 45792 KB Output is correct
18 Correct 91 ms 38188 KB Output is correct
19 Correct 467 ms 135720 KB Output is correct
20 Execution timed out 547 ms 135512 KB Time limit exceeded
21 Halted 0 ms 0 KB -