Submission #1267008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267008		shiori_chan	Paths (BOI18_paths)	C++17	23 / 100	130 ms	25276 KiB

paths

#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 = 3e5 + 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;
}

int col[nd];
vi adj[nd];

int dp[33][nd];

void solve(){
    int n , m , k;
    cin >> n >> m >> k;

    FOR(i , 1 , n) cin >> col[i] , -- col[i] , dp[1 << col[i]][i] = 1;
    FOR(i , 1 , m){
        int l , r;
        cin >> l >> r;
        adj[l].eb(r) , adj[r].eb(l);
    }

    int res = 0;

    FOR(mask , 1 , (1 << k) - 1){
        FOR(r , 1 , n){
            if(__builtin_popcount(mask) != 1) res += dp[mask][r];
            for(int v : adj[r]) if(!(mask & (1 << col[v]))){
                dp[mask | (1 << col[v])][v] += dp[mask][r];
            }
        }
    }

    cout << res;
}

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)

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

• Subtask 1: 23 / 23
• Subtask 2: 0 / 20
• Subtask 3: 0 / 27
• Subtask 4: 0 / 30