Submission #1268284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268284		shiori_chan	Senior Postmen (BOI14_postmen)	C++17	100 / 100	344 ms	88544 KiB

postmen

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pb push_back
#define fi first
#define se second
#define compact(v) v.erase(unique(all(v)) , v.end())
#define pi pair<int , int>
#define vi vector<int>
#define eb emplace_back
#define FOR(i , l , r) for(int i = l; i <= r; ++ i)
#define FORD(i , l , r) for(int i = l; i >= r; -- i)

using namespace std;
typedef long long ll;

const int nd = 5e5 + 1 , mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> dist(1 , (int)2e9);

template <class T> bool maximize(T &a , T b){return (a < b ? a = b , true : false);}
template <class T> bool minimize(T &a , T b){return (a > b ? a = b , true : false);}


int add(int a , int b) {return (a + b) % mod;}
int mul(int a , int b) {return (a * b) % mod;}
int sub(int a , int b) {return (a - b + mod) % mod;}
int xpow(int a , int b){
    int res = 1;
    for(int i = 0; (1 << i) <= b; ++ i){
        if(b & (1 << i)) res = mul(res , a);
        a = mul(a , a);
    }
    return res;
}

vector <pi> adj[nd];
int vs[nd];
bool used[nd];
int st[nd];
int last;
int cur = 0;
int timer = 0;
vi ans[nd];

bool dfs(int r){
    vs[r] = cur;
    //cout << r << '\n';

    for(; st[r] < adj[r].size(); ++ st[r]){
        auto [v , id] = adj[r][st[r]];

        if(used[id]) continue;
        used[id] = true;

        if(vs[v] == cur){
            ++ timer;
            ans[timer].eb(r);
            last = v;
            vs[r] = false;
            return false;
        }

        if(!dfs(v)){
            ans[timer].eb(r);
            if(last != r){
                vs[r] = false;
                return false;
            }
        }
    }

    return true;
}

void solve(){
    int n , m;
    cin >> n >> m;
    FOR(i , 1 , m){
        int l , r;
        cin >> l >> r;
        adj[l].pb({r , i});
        adj[r].pb({l , i});
    }

    FOR(i , 1 , n) if(st[i] < adj[i].size()){
        ++ cur;
        dfs(i);
    }

    FOR(i , 1 , timer){
        for(int v : ans[i]) cout << v << " ";
        cout << '\n';
    }
}

signed main() {
   ios_base::sync_with_stdio(false);
   cin.tie(0);

    #define task "task"
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    int test_case = 1;
    while(test_case --) solve();

    return 0;
}
/*
               -.                                                                             ::.            -:       .::::::::::
 ***##*###**##@%***+###+***+**++******#*******#*******++*****+*+=@*+####%@@@@@%*===#*%@===---**#@@#=*######***@@@#*###=*@%#######:
 **##*##*+*%#%@**+**##****************#***+***#*+*+***+++******+=@#+*#=:--===-====-*#+@%:#@@%##*#%#+########+*@%@#*##+=@%######:
 #%####*+*%##@#+*+*###**#********##***#++***++#********#***+++++=%@=###==========:#:#+*@######*%##%#=+###*##*+#@##@%###+=%#####:
 #####***%##@%+***#%#++#######*********++***#*#+##%##****#####+#@ ###===++++=-=@@#**+#%+*+##+#%##%#+*######*+%###@###*=#%####:
 ##*****####@*+***###+=**#+==*+*###%#%###%**%*#=::-+#%####+#=-#+@=-###===+==-#@#*###+=@#+*+##*#%##%##=*######*+@%###%*#*+%###:
 %##***####@#++*+#%+*++=+++=+#**#===-==+*+=:=+@-#+-===-:+#%+:+#:#=@@.#%#----:-###*****#=*@+++***+#%#%#%#+*###*##**@####%@#***%###:
 *####*@##%@++***##+###+====##+##==========-+*@:%+-=-::::::::=@:#=@%+=##**==#@#####*###+=@%=****#+%##@#%#=####*##+#%#####%##**%##:
 #**#*#%##@#*#***##**########*+#*-=*+==+===-++@.%=::+@#+=:.=@*#=#=@%#=*@*####**+*********+@*=+*****%#%*%+*####****@######%**#%#:
 ####*####@++*+*#%+*#**********##*####-====:*=@.#-:####%@@%#####=%#=+@#=+***++*******+#=%@+++*++=*%#@###=*######+@%######@#+###.
 ###**%##@#*****#@*##*#**#***+*******##*==##*=@=%#%##*##*##+*##*-%@%==#@+=*+******#****##+@%+=+***+##%*##*#**##**+@#######@**##:
 ###*#%##@++#*+*##*##****##****#*******####*+=@=%+********#*=*##*-#@#*:*@#=+***+**+++***=@=@@@#=++++=@#@#+%***#####+@#######%#+##.
 ###*#%#%**##+*%#**#*#**#***********#******+=@=%=*++**#**#*+**++-#@*@-=@#=+***+++*+****=#*@ @@#=*##+*#@%++#**#####*%#######@+##:
 ###*###@#**##+*@*************#************#==@+@=+*+++***#+++*++=@@*##:%@#=++++++++++**+*%@@ @@%-=+++##@#=%+*#*#***#%#######%##%:
 ##*#%##@***##+#%**#***#***#********+***#+*#==@#@:=+++++**@=+++++*#@@*%-+@@==++**+**++**++%@@  @@@=-=+##@%=##+#*#***#%###########.
 ##*#%##@*#*##=*%**#*******+***********+*+*+=-@#@-=++++=+%*=+***+@. @###:@%=******+*****=#@@    @@@*:-#@%+=%+#*###+#@###########:
:@#*#%##%#**##+#%+************#*****++***+#*+-%@==+++*=+@=++++==@  @@#%=##%==+*++*+*****=#@@     @@@@#*#@*-@+***##+#%########%#:
 #@*##%@#*###*+#%*##****+***++***++**+++++++*-%@@*=++++=%-==**#@@@@@@##%+#%-=+++++**+**==@@        @#*+@*=##***##+*@###########:
  @*%#%##*##**#%**####*#***********++**+**+*-#@%#-+++=:@=#%##+#@    @@#####@#=++**+******-@=  *@@@@@@@@@@@=+#****#*+@###########:
 @@@%##@#**##*+#%**************+*****+++++++*=#@#@:=+==@@-====*@     @@######@+=+++++++*++=@  @@@@@@@@  +@@=+#****#*=%##########:
  #@@%#@##*###+#@***********+*#*++++++***+*+#=*@#%++=:@@==+*++@@  ..  @@#####%@-=***+*****=@@@@@@   .@@.@ @#=***#+#*=@@##########:
    @%#@#*##**+#@#**#*******+*#++****++++*++#=+@##@ :@@*-+==+@@   .:   @@#####@@=+++++*++**=@@%@@@   -@@@:*@=*#**+#*+@*@#########:
 =:  ##@**####+#@***********+*#++***+++++*++#+=@##@%@@#:=++*@@     ..  #@@#####@#=+**+*+#@@%#@##@@   @  @-=@=****+%*=@-#@%#######:
 : :@@*@##****+#@*+****#****+*%+*****+++++++#==@###%@@-=*+*@@   -*+     =@@#####@*=+**++#= -@%   :  @% -@==@=#***+@*=@% +@@######:
  @@@*+@##**+*+#@#+*******+*++@=+***++**++++**=@##@@*-=+==*.        *::  -@@*####%#-++++##=:%   @-@@%  *@=-@=#***+@+=%@@. @@@%###:
+@@#*+*@##*###=#@#=****#****++@*=*+*++++++++*+=@@@%-:==--+@@@@@@@@#        @@####%*-=+++#+=@@ :       +@+=@+#**++@+=@#%@%- -##%:
 ##%#*#@##**##=#@%+*********+=%#=*++++++*++====@@::-=+##@@@@@@@@@@@@@@      @@@*##%##===++**#@      .. :@*-@%***+*@==@###%@@%####:
 ###%@%@##****=#@@++*#*******=#@=++++*+*+===#@%-:-##+=#@#===@      ::++      =@@***#*#=-==++=@@         @#=#@*+*=#%==@@%#*###%@##.
 #*@ @@@#**###=#@%*+*********+=@+=***+-==#@@+---=+++#@@@@@@@@@                 @@@*+%##*--=+==@+   .    @@+#@*=+=@#==@###%#####.
 **@  @@%****#+#@@#+*********+-@#:====@@#==-===++#@@@@@  @  @@                   @@@+*#+**:-==*@     .  @@**@+=+*%#=+@###########.
 ++@: @@%+*#**++@%@=**+++++===-%@@@@@#=-==+=--+#@@@    @@       . .                @@@@#=+**=--#@       +@**@+==##*-#@###########:
-@@@   @#-======%@*===*###@@@@#=----==+==-=#@@@@ @@*      :@=                        @@@@@#*#=:#@       @*#@==+%#+*#@%##########:
 %@@@@@@#%@@@@@@@%@@@@@%##+=---=+=====-=+@@@#=#*@   ::.+@#:                              :#@@@@#+#@@     @#@@--%#=#*%###########:
%@@  @%@#%##++======------=========#%@@@@=====*=@#%@@%-                             ...       @@@@@@@@#  @*@#:=@#**#*@###########.
   @@%-@*=*#@@@@%#*+*#%@@@@@@@@@@@@@+=--=+***+##@                                  .        .       .*%  @@@:-@##=#+#@#%#########.
 @@@**=@++++=:=%##@@@##%##*+==@%==++******+*#@                                 ..     .  #            @@*:##**##+#%##########%.
+@@#***@+***++@####@*@#=-==+++*+=%@@=+*******++#@=                                 .   ..  =.           @@@.:@*#*##+@%###########
:%#**#%@=**+=%###@@+@#%++******=*@@#=********+%@@                                         .            @@.:@**###*+@###*%#######.
:#+*##@%+**=%###*@+##@#%*=*#***+=@%@++******+++@@                                                     @@:.@@=#**#=@@############.
 ++##%@*++=#@###*%@*##@##%#=+****=#%#=**+*****+%@                                                    @@.=@@@=*##*=@######%######
 #%@@@++=%@#####@#####@*##%+++**+*@%@*=+******+=@+                                          .       @@.#%#@%=###=#%#%####%######
:@@@-@#==@@####*@*#%####@*##%*=+*+=#@#@*=++****+=%@                                        @        %@@@##@@++##=-@###%##########
 +-=@@=+@%####*%###%@*##%==+=#%#%+=+*****==@                                  :=-::         @@@@*#%#@=*#+-@########=@#####
 **%@#*%####*#@%@*%#%##@#*##%@*==+%###@*=+*++*+-@@                           :::                @@%#@###%+#=.@%########+%#####
 #@@########*@@@@%:@%###@%####%@+:##@##%*=+*+++==@                                            :@@%@####@**-:@%######%*#*######
 @%#######**@@#@+=-@%######@######@#=##%##@%==+++==@@                                      @@  =@@%######@@+ =@%#################
=%#######+@@##@#+*=@##%####@%##############@=======@                                     @%@-@@@#######@%: @@##########%#*######
.######*%@@%#%@+**=@#######@.@%##########%**#%#=====*@  :.                                **@@:@@@#####@# +@%#############*######
.#%##+@@@%=#%@#*#**@#%####@:=%@##%##*######*##@*=-==#@   :=@@:                           @ -##-@@@###%-=@%############*##+%#####
:#=*@@#*=+=%#**#+#@#@#####@-==%@**#%#*****##**##%*:--#@       :+%@@@*                     :      @@@#*###################+%#####
 @@###+*#*#@%##*#+%@*%###@=++=%@#*#%#*+********##*-:=@+             @@@@#:             +@       *@@@#############**######*####
 #####***+@@**##**%@@-#%###@=***-%@%***@%#++***#++**###-=%@           @   .-+#%@@@@@@@@@@@@@@        #@@@%#############*#*#####**
 ####%*#*#@#**##*#%@::@%###@=#+#=-##@*+*#@@#*=++##=+**##*=*@%       @@  :::::::.  #@  @@%###@@          @@@@#########**##********
.#####**#@#*####+#@@ #@##%@@=#=%=+=#*@@@@%+%@@@@%*#@===+**+#%@@    @%:.::::::--:: @@ =@*#=#*@@@@          +@@@#*#*******###*###**
 #####**%#**##***@@= @%##@:#+%=@++=#*@* @@@@#*  @@@@#@@+=+****@@@+ :              @@ +@#=:%#@ @@@%           @@@%#######**#**+***
.####**%**###**%@@  @%#@@ #%#=##==#*@@    @@@@@    @@@@@@@+==+*#@@@@@=:    :#@@@ @@ =@#=-###@ #@@@@           @@@@#*************
 ####*#%*#####+#@@  =@%@ @+@#=+#==#*@* .     +@@@@        *@@@*=++==#@@@@@@@:    @@:-@#=-*##@= @@#@@@           #@@@#***********
.#######**###**@@=  @@@@+ ##@#=+#*=##@    ::.     :@@@@@@@-    :@*@@@@@@=       : -@@=#+==+##*@@: %==@@@@           @@@@#****++++
 ######*##*##*@@#  *@@@= @#@@#=++@+##@ +#=    @@@@#+-*%@@@@@@@@@%.       %@@@@@@%= @=@#+===##++=%@:@=:#@@@@           -@@@@%#****
 #####**##*+*#@%  =@%@@.*@@ @%+++=#*@@ .    @@@==@@@@@@-                         .@@@@@+===*+@=## @@@#-+%*@@@:            =@@@*++
 ####***#*+*#@@  :@#@@+ %#@ @@#+++*#@@ -. @@@##@@@#                                  @@@+====@.#@=  @@%==#**@@@-   :=:::.    @@*+
 ##*+*##*++@@@  #@#@@@  @#@  @@#++=*%@   *@%@@@        .                              @@#===#=:@@@   @@@%@@@@@@@@=     .-:   #@*
.##**#****%@@. @@*@@=  .@#@   @@@+=++@  @@%@@@      ......::                            #@@===@  @@@@ ::#@@=         .   .:-.  @@
 #+***++#%@@  @##@@    %@#@ *:  @@@+=*@@@@@@    ....     . ..::.                          @@+-*@  @@@.                ...   .   #
 *#****##% +@*#@%  .: @@#@      :@@@#@@@@     ...  ..         .:.                         @@#=#@  -                   .......
 **++##### @##@@:  ::: =@#@  .:     @@@     ......... .  ..      ..                         @%#*@: # :            .=**=:.. ..:.
 ++*####**#**@@   ::::  @@@@     @@@:    .:.......... ... . .     .:                        -@#+#@ : .:::..:=#%@@@@=    .........
 +######*+*@@*  :::::::   @@@@@@@@    ..:....... .....  .   ...   . .                        %+**%@  ..   #  -**       . . ..:...
 ##**#*+=#@@:  ::::::::. .          :...:........... .  ..         ..                        ##-=#@  .   =@@=            . ......
 ####*+#@@*  :::-::::: ==-=: .::.:::..            ... .. ....       ...                      ##=-=@   :#+.          .::.  ...::::
                                                                                                                                  */

Compilation message (stderr)

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

• Subtask 1: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 45 / 45