結果
| 問題 | No.95 Alice and Graph |
| ユーザー |
 Shlok Goyal
|
| 提出日時 | 2021-10-25 20:07:36 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 1,616 ms / 5,000 ms |
| コード長 | 5,558 bytes |
| コンパイル時間 | 3,632 ms |
| コンパイル使用メモリ | 224,792 KB |
| 実行使用メモリ | 12,388 KB |
| 最終ジャッジ日時 | 2024-04-14 16:41:31 |
| 合計ジャッジ時間 | 9,366 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 491 ms
12,196 KB |
| testcase_01 | AC | 76 ms
12,388 KB |
| testcase_02 | AC | 76 ms
12,316 KB |
| testcase_03 | AC | 27 ms
12,176 KB |
| testcase_04 | AC | 735 ms
12,168 KB |
| testcase_05 | AC | 586 ms
12,180 KB |
| testcase_06 | AC | 716 ms
12,260 KB |
| testcase_07 | AC | 76 ms
12,180 KB |
| testcase_08 | AC | 2 ms
6,944 KB |
| testcase_09 | AC | 2 ms
6,944 KB |
| testcase_10 | AC | 2 ms
6,944 KB |
| testcase_11 | AC | 2 ms
6,944 KB |
| testcase_12 | AC | 2 ms
6,940 KB |
| testcase_13 | AC | 1,616 ms
12,352 KB |
ソースコード
//*** 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;
}