結果

問題 No.95 Alice and Graph
コンテスト
ユーザー Shlok Goyal
提出日時 2021-10-25 20:07:36
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 1,612 ms / 5,000 ms
コード長 5,558 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,129 ms
コンパイル使用メモリ 219,840 KB
最終ジャッジ日時 2025-01-25 06:48:51
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

//*** Author: ShlokG ***//
// #pragma GCC optimize("Ofast")  
// #pragma GCC target("avx,avx2,fma") 
// #pragma GCC optimization ("unroll-loops")
#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;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// find_by_order(k)  returns iterator to kth element starting from 0
// order_of_key(k) returns count of elements strictly smaller than k
#define fix(f,n) std::fixed<<std::setprecision(n)<<f
#define epsi (double)(0.00000000001)
typedef long long int ll;
typedef unsigned long long int ull;
#define vi vector<ll>
#define pii pair<ll,ll>
#define vii vector<pii>
#define vvi vector<vi>
//#define max(a,b) ((a>b)?a:b)
//#define min(a,b) ((a>b)?b:a)
#define min3(a,b,c) min(min(a,b),c)
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define max3(a,b,c) max(max(a,b),c)
#define max4(a,b,c,d) max(max(a,b),max(c,d))
#define ff(a,b,c) for(int a=b; a<=c; a++)
#define frev(a,b,c) for(int a=c; a>=b; a--)
#define REP(a,b,c) for(int a=b; a<c; a++)
#define pb push_back
#define mp make_pair
#define endl "\n"
#define all(v) v.begin(),v.end()
#define sz(a) (ll)a.size()
#define F first
#define S second
#define ld long double
#define INf 2000000000000000000
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define ub upper_bound
#define lb lower_bound
#define setbits(x) __builtin_popcountll(x)
//#define trav(a,x) for(auto &a:x)
#define make_unique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define rev(arr) reverse(all(arr))
#define gcd(a,b) __gcd(a,b);
#define ub  upper_bound // '>'
#define lb  lower_bound // '>='
#define qi queue<ll>
#define si stack<ll>
//FLags -> -Wfloat-equal -fsanitize=address -fsanitize=undefined
// Swap only swaps data but not memory pointer to that data structures

const long double PI = acos(-1);

mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
    uniform_int_distribution<int> uid(0,lim-1);
    return uid(rang);
}

ll gcdExtended(ll a, ll b, ll *x, ll *y){
    if(a == 0){
        *x = 0;
        *y = 1;
        return b;
    }
    ll x1, y1;
    ll gcd = gcdExtended(b%a, a, &x1, &y1);
    *x = y1 - (b/a) * x1;
    *y = x1;
    return gcd;
}
 
ll modInverse(ll a, ll m){
    ll x, y;
    ll g = gcdExtended(a, m, &x, &y);
        ll res = (x%m + m) % m;
        return res;
}

ll binary_Search(vector<ll>&arr,ll key){
    ll l=0,r=arr.size()-1;
    ll ans;
    while(l<=r){
        ll mid=(l+r)/2;
        ll value=arr[mid];
        if(value>key){
            r=mid-1;
        }else if(value==key){
            return mid;
        }else{
            l=mid+1;
        }
    }
    return -1;
}
 
ll power(ll x,ll y,ll p){
    ll res = 1;
    x = x % p;
    if (x == 0) return 0;
    while (y > 0){  
        if (y & 1){
            res=(res*x)%p;
        }
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}

// ll check(ll x){
//     ll tem=sqrt(x);
//     while((tem*tem)<=x) tem++;
//     while((tem*tem)>x) tem--;
//     return tem;
// }

// ll check1(ll x){
//     ll tem=sqrt(x);
//     while((tem*tem)<=x) tem++;
//     while(((tem-1)*(tem-1))>=x) tem--;
//     return tem;
// }

const ll MAX=1e18+5;
//const int N=1e6+5;
const int N1=5*1e3+5;
//vector<int> pr;

// ll prime[N+5];
// void SieveOfEratosthenes(){ 
//     memset(prime, 0, sizeof(prime)); 
//     prime[1]=1;
//     for(ll p=2 ; p<N ; p++){
//         if(prime[p] == 0){
//             for(ll i=p ; i<N ; i+=p){
//                 if(prime[i]==0){
//                     prime[i]=p;
//                 }
//             }
//         }
//     }
//     // for(int i=2 ; i<N;  i++){
//     //     if(!prime[i]){
//     //         pr.pb(i);
//     //     }
//     // }
// }

ll mod=1e9+7;
ll mod1=998244353;

const int infi = 1e9;
const ll INF=1e18;

void precompute(){

}

#define FOR(a,b) for(int a=0; a<b ; a++)

int N, M, K;
 int mat [ 100 ] [ 100 ];
 int dp [ 1 << 17 ] [ 17 ];
vector < int > V;

void TEST_CASE(){
    int i, j, k, l, r, x, y; string s;
    
    cin >> N >> M >> K;
    FOR (x, 100 ) FOR (y, 100 ) mat [x] [y] = 1000 ;
    FOR (x, 100 ) mat [x] [x] = 0 ;
    FOR (i, M) {
        cin >> x >> y;
        mat [x- 1 ] [y- 1 ] = mat [y- 1 ] [x- 1 ] = 1 ;
    }
    FOR (i, N) FOR (x, N) FOR (y, N) mat [x] [y] = min (mat [x] [y], mat [x] [i] + mat [i] [y ]);
    V.push_back ( 0 );
    
    ll ret = 0 ;
     for (i = N- 1 ; i> 0 ; i--) {
         if (V.size() >= K + 1 ) break ;
        
        V.push_back (i);
        memset (dp, 0x3f , sizeof (dp));
        dp [ 1 ] [ 0 ] = 0 ;
         for ( int mask = 1 ; mask < 1 << V.size (); mask ++) {
            FOR (x, V.size ()) if (mask & ( 1 << x)) {
                FOR (y, V.size ()) if (x!= y && (mask & ( 1 << y))) dp [mask] [x] = min (dp [mask] [x], dp [mask ^ ( 1 << x)] [y] + mat [V [x]] [V [y]]);
            }
        }
        
        int ok = 0 ;
        FOR (j, V.size ()) if (dp [( 1 << V.size ())- 1 ] [j] <= K) ok ++;
         if (ok == 0 ) V.pop_back ();
         else ret += ( 1LL << i) -1 ;
    }
    
    cout << ret << endl;
}

signed main(){
    fast;
    //freopen ("INPUT.txt","r",stdin);
    //freopen ("OUTPUT.txt","w",stdout);
    int test=1,TEST=1;
    precompute();
    //cin >> test;
    while(test--){
        //cout << "Case #" << TEST++ << ": ";
        TEST_CASE();
    }
    return 0;
}
0