### lazy_dumbo's blog

By lazy_dumbo, history, 5 weeks ago, ,  mst, Comments (1)
 » 5 weeks ago, # | ← Rev. 4 →   Please, do not do s|=(1<<(x)); with long long values, use s|=(1ll<<(x));As far as I understood the problem you need bucket sort for highest setted bit. Then you can ask yourself whether you can construct the connected graph not using the roads with highest cost token (with id $k-1$) or not (ala MST by means of DSU). If so you can exclude this token from the final list. And then you can try to construct connected graph not using the roads with token id $k-2$. And so on. Finally you will have the list of not used tokens. The complexity is $O(k*m*DSUfactor)$, where $DSUfactor$ is $log(n)$ for your DSU implementation. Code#include #if defined( _WIN32 ) typedef __int64 az_int64_t; typedef unsigned __int64 az_uint64_t; #define I64(x) x ## I64 #define F64 "I64" #else typedef long long az_int64_t; typedef unsigned long long az_uint64_t; #define I64(x) x ## ll #define F64 "ll" #endif #define MAXN (100*1024) struct link { az_int64_t t; int u, v; }; struct link links[MAXN]; int n, m, k; az_int64_t c; int gr[MAXN]; int getgr( int g ) { return (g == gr[g]) ? g : (gr[g] = getgr( gr[g] )); } int test( az_int64_t r ) { int i, left = n-1, u, v; for( i = 1; i <= n; ++i) gr[i] = i; for( i = 0; i < m; ++i) if( (links[i].t & r) == 0 && (u = getgr( links[i].u )) != (v = getgr( links[i].v )) ) { gr[v] = u; if( --left == 0 ) return 1; } return 0; } int main( void ) { az_int64_t rejected = 0, sum = 0; int i; scanf( "%d %d %d", &n, &m, &k); for( i = 0; i < k; ++i) scanf( "%" F64 "d", &c[i]); for( i = 0; i < m; ++i) { int l, id; scanf( "%d %d %d", &links[i].u, &links[i].v, &l); while( l-- > 0 ) { scanf( "%d", &id); links[i].t |= I64(1) << (id-1); } } if( !test( 0 ) ) { printf( "-1\n" ); return 0; } for( i = k-1; i >= 0; --i) { az_int64_t f = I64(1) << i; if( test( rejected | f ) ) rejected |= f; else sum += c[i]; } printf( "%" F64 "d\n", sum); return 0; } UPD: added code and fixed some errors.