oj.uz

Submission #25387

# Submission time Handle Problem Language Result Execution time Memory
25387 2017-06-21T20:31:13 Z tuna_salad Cities (BOI16_cities) C++14
74 / 100
 4000 ms 232384 KB 
//spnauT
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int _=b,i=a;i<_;++i)
#define ROF(i,b,a) for(int _=a,i=b;i>_;--i)
#define REP(n) for(int _=(n);_--;)
#define _1 first
#define _2 second
#define PB push_back
#define SZ(x) int((x).size())
#define ALL(x) begin(x),end(x)
#define MSET(m,v) memset(m,v,sizeof(m))
#define MAX_PQ(T) priority_queue<T>
#define MIN_PQ(T) priority_queue<T,vector<T>,greater<T>>
#define IO {ios_base::sync_with_stdio(0);cin.tie(0);}
#define nl '\n'
#define cint1(a) int a;cin>>a
#define cint2(a,b) int a,b;cin>>a>>b
#define cint3(a,b,c) int a,b,c;cin>>a>>b>>c
using namespace std;using LL=int64_t;using PII=pair<int,int>;
using VI=vector<int>;using VL=vector<LL>;using VP=vector<PII>;
template<class A,class B>bool mina(A&x,B&&y){return y<x?(x=forward<B>(y),1):0;}
template<class A,class B>bool maxa(A&x,B&&y){return x<y?(x=forward<B>(y),1):0;}

const int MAX_N {100004};
const int MAX_M {200004};
const int MAX_K {5};
const int MAX_2_K {1 << 5};
const int MASK_K {MAX_2_K - 1};
const LL infLL {1LL << 50};

VP E[MAX_N];
VP B[MAX_2_K];

LL dist[MAX_N << MAX_K];

int main()
{
	IO;
	cint3(N,K,M);
	VI I;
	REP(K)
	{
		cint1(a);
		--a;
		I.PB(a);
	}
	REP(M)
	{
		cint3(a,b,c);
		--a; --b;
		E[a].PB({b,c});
		E[b].PB({a,c});
	}

	FOR(a,0,1<<K) FOR(b,0,1<<K) if(not (a & b)) B[a].PB({b,a|b});

	fill(ALL(dist), infLL);
	using P2 = pair<LL,int>;

	MIN_PQ(P2) Q;
	auto f = [&](LL d, int u, int b)
	{
		int s {(u << MAX_K) | b};
		if(mina(dist[s],d)) Q.push({d,s});
	};
	FOR(i,0,N) dist[i << MAX_K] = 0;
	FOR(j,0,K) f(0, I[j], 1<<j);

	const int bit_goal {(1 << K) - 1};
	while(!Q.empty())
	{
		LL d;
		int s;
		tie(d,s) = Q.top();
		Q.pop();
		if(dist[s] < d) continue;

		int u {s >> MAX_K};
		int b {s & MASK_K};

		if(b == bit_goal)
		{
			cout << d << nl;
			break;
		}

		int s1 {u << MAX_K};
		for(PII eb: B[b])
		{
			LL d1 {d + dist[s1 ^ eb._1]};
			if(d1 < infLL) f(d1, u, eb._2);
		}

		for(PII e: E[u])
		{
			int v {e._1};
			LL d1 {d + e._2};
			int s2 {v << MAX_K};
			for(PII eb: B[b])
			{
				LL d2 {d1 + dist[s2 ^ eb._1]};
				if(d2 < infLL) f(d2, v, eb._2);
			}
		}
	}

	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 29528 KB Output is correct
2 Correct 0 ms 29528 KB Output is correct
3 Correct 6 ms 29528 KB Output is correct
4 Correct 6 ms 29528 KB Output is correct
5 Correct 6 ms 29528 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 763 ms 60356 KB Output is correct
2 Correct 759 ms 60300 KB Output is correct
3 Correct 146 ms 34228 KB Output is correct
4 Correct 119 ms 35472 KB Output is correct
5 Correct 313 ms 41920 KB Output is correct
6 Correct 89 ms 34304 KB Output is correct
7 Correct 6 ms 29792 KB Output is correct
8 Correct 9 ms 29660 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 30404 KB Output is correct
2 Correct 16 ms 30400 KB Output is correct
3 Correct 3 ms 29980 KB Output is correct
4 Correct 13 ms 30408 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2809 ms 134080 KB Output is correct
2 Correct 2456 ms 133884 KB Output is correct
3 Correct 1316 ms 57272 KB Output is correct
4 Correct 1679 ms 84452 KB Output is correct
5 Correct 329 ms 59320 KB Output is correct
6 Correct 156 ms 38696 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4000 ms 232384 KB Execution timed out
2 Halted 0 ms 0 KB -