結果

問題 No.2630 Colorful Vertices and Cheapest Paths
ユーザー ゆにぽけゆにぽけ
提出日時 2024-02-16 21:59:56
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 269 ms / 2,500 ms
コード長 7,999 bytes
コンパイル時間 1,542 ms
コンパイル使用メモリ 147,536 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-09-28 20:17:30
合計ジャッジ時間 6,206 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 94 ms
6,820 KB
testcase_01 AC 226 ms
6,820 KB
testcase_02 AC 225 ms
6,816 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 2 ms
6,816 KB
testcase_05 AC 2 ms
6,820 KB
testcase_06 AC 110 ms
6,820 KB
testcase_07 AC 188 ms
6,820 KB
testcase_08 AC 177 ms
6,820 KB
testcase_09 AC 189 ms
6,816 KB
testcase_10 AC 267 ms
6,816 KB
testcase_11 AC 269 ms
6,816 KB
testcase_12 AC 265 ms
6,820 KB
testcase_13 AC 264 ms
6,816 KB
testcase_14 AC 260 ms
6,820 KB
testcase_15 AC 233 ms
6,816 KB
testcase_16 AC 225 ms
6,816 KB
testcase_17 AC 231 ms
6,816 KB
testcase_18 AC 112 ms
6,820 KB
testcase_19 AC 158 ms
6,816 KB
testcase_20 AC 142 ms
6,816 KB
testcase_21 AC 178 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <iterator>
#include <string>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <cmath>
#include <ctime>
#include <iomanip>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <bitset>
#include <random>
#include <utility>
#include <functional>
using namespace std;
template<class T>
inline bool chmin(T &a,const T &b)
{
	if(a > b)
	{
		a = b;
		return true;
	}
	return false;
}
template<class T>
inline bool chmax(T &a,const T &b)
{
	if(a < b)
	{
		a = b;
		return true;
	}
	return false;
}
template<class T>
void print(const vector<T> &V)
{
	for(int i = 0;i < (int)V.size();i++)
	{
		cerr << V[i] << (i + 1 == (int)V.size() ? "\n":" ");
	}
}
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cassert>
#include <cmath>
using namespace std;

namespace geometry
{
	using real = long double;
	const real EPS = 1e-9;
	bool EQ(real a,real b)
	{
		return abs(a - b) < EPS;
	}

	struct Point
	{
		real x,y;

		Point(real x_ = 0,real y_ = 0) : x(x_),y(y_) {}

		Point operator-() const
		{
			return Point(-x,-y);
		}

		Point operator+(const Point &rhs) const
		{
			return Point(x + rhs.x,y + rhs.y);
		}

		Point operator-(const Point &rhs) const
		{
			return Point(x - rhs.x,y - rhs.y);
		}

		Point operator*(const real k) const
		{
			return Point(x * k,y * k);
		}

		Point operator/(const real k) const
		{
			assert(!EQ(0,k));
			return Point(x / k,y / k);
		}

		bool operator<(const Point &rhs) const
		{
			return EQ(x,rhs.x) ? y < rhs.y : x < rhs.x;
		}

		bool operator==(const Point &rhs) const
		{
			return EQ(x,rhs.x) && EQ(y,rhs.y);
		}
	};

	istream &operator>>(istream &is,Point &p)
	{
		return is >> p.x >> p.y;
	}

	ostream &operator<<(ostream &os,const Point &p)
	{
		return os << p.x << " " << p.y;
	}

	struct Line
	{
		Point p1,p2;
		Line(Point p1_ = Point(),Point p2_ = Point()) : p1(p1_),p2(p2_) {}
	};

	struct Segment : Line
	{
		Segment(Point p1_ = Point(),Point p2_ = Point()) : Line(p1_,p2_) {}
	};

	struct Circle
	{
		Point O;
		real r;
		Circle(Point O_ = Point(),real r_ = 0) : O(O_),r(r_) {}
	};

	using Polygon = vector<Point>;

	Point vec(const Line &l)
	{
		return l.p2 - l.p1;
	}
	real norm2(const Point &p)
	{
		return p.x * p.x + p.y * p.y;
	}
	real abs(const Point &p)
	{
		return hypot(p.x,p.y);
	}

	real dot(const Point &a,const Point &b)
	{
		return a.x * b.x + a.y * b.y;
	}
	
	real cross(const Point &a,const Point &b)
	{
		return a.x * b.y - a.y * b.x;
	}

	Point rotate(const Point &p,const real &theta)
	{
		return Point(p.x * cos(theta) - p.y * sin(theta), p.x * sin(theta) + p.y * cos(theta));
	}

	Point rotate(const Point &a,const Point &p,const real &theta)
	{
		Point q = rotate(p - a,theta);
		return a + q;
	}

	enum
	{
		ONLINE_FRONT = -2,
		CLOCKWISE= -1,
		ON_SEGMENT = 0,
		COUNTER_CLOCKWISE = 1,
		ONLINE_BACK = 2
	};

	int ccw(const Point &a,const Point &b)
	{
		real C = cross(a,b);
		return C > EPS ? COUNTER_CLOCKWISE : C < -EPS ? CLOCKWISE : dot(a,b) < -EPS ? ONLINE_BACK : norm2(b) - norm2(a) > EPS ? ONLINE_FRONT : ON_SEGMENT;
	}

	int ccw(const Point &a,const Point &b,const Point &c)
	{
		return ccw(b - a,c - a);
	}

	bool orthogonal(const Point &a,const Point &b)
	{
		return EQ(dot(a,b),0);
	}
	
	bool orthogonal(const Line &a,const Line &b)
	{
		return orthogonal(vec(a),vec(b));
	}

	bool parallel(const Point &a,const Point &b)
	{
		return EQ(cross(a,b),0);
	}

	bool parallel(const Line &a,const Line &b)
	{
		return parallel(vec(a),vec(b));
	}

	bool intersect(const Line &l,const Point &p)
	{
		return parallel(vec(l),p - l.p1);
	}

	bool intersect(const Segment &s,const Point &p)
	{
		return ccw(s.p1,s.p2,p) == ON_SEGMENT;
	}

	bool intersect(const Segment &a,const Segment &b)
	{
		return ccw(a.p1,a.p2,b.p1) * ccw(a.p1,a.p2,b.p2) <= 0 && ccw(b.p1,b.p2,a.p1) * ccw(b.p1,b.p2,a.p2) <= 0;
	}

	Point cross_point(const Line &a,const Line &b)
	{
		real s1 = cross(vec(a),b.p1 - a.p1);
		real s2 = -cross(vec(a),b.p2 - a.p1);
		return b.p1 + vec(b) * (s1 / (s1 + s2));
	}

	Point crossPoint(const Line &s, const Line &t) {
		real d1 = cross(s.p2 - s.p1, t.p2 - t.p1);
		real d2 = cross(s.p2 - s.p1, s.p2 - t.p1);
		if(EQ(abs(d1), 0) && EQ(abs(d2), 0)) {
			return t.p1;
		}
		return t.p1 + (t.p2 - t.p1) * (d2 / d1);
	}


	enum
	{
		OUT,
		ON,
		IN
	};

	Polygon convex_hull(Polygon P,bool ONLINE = false,bool SORT = false)
	{
		if((int)P.size() <= 2)
		{
			return P;
		}
		sort(P.begin(),P.end());
		Polygon res(2 * P.size());
		int sz = 0;
		real threshold = EPS;
		if(ONLINE)
		{
			threshold = -EPS;
		}

		for(int i = 0;i < (int)P.size();i++)
		{
			while(sz >= 2 && cross(res[sz - 1] - res[sz - 2],P[i] - res[sz - 1]) < threshold)
			{
				sz--;
			}
			res[sz++] = P[i];
		}
		for(int i = (int)P.size() - 2,t = sz + 1;i >= 0;i--)
		{
			while(sz >= t && cross(res[sz - 1] - res[sz - 2],P[i] - res[sz - 1]) < threshold)
			{
				sz--;
			}
			res[sz++] = P[i];
		}
		res.resize(sz - 1);
		if(SORT)
		{
			int mi = 0;
			for(int i = 1;i < (int)res.size();i++)
			{
				if((EQ(res[mi].y,res[i].y) && res[mi].x > res[i].x) || res[mi].y > res[i].y)
				{
					mi = i;
				}
			}
			rotate(res.begin(),res.begin() + mi,res.end());
		}
		return res;
	}

	int convex_contain(const Polygon &P,const Point &p)
	{
		if(P[0] == p)
		{
			return ON;
		}

		int L = 0,R = (int)P.size();
		while(R - L > 1)
		{
			int M = (L + R) / 2;
			if(ccw(P[0],P[M],p) == CLOCKWISE)
			{
				R = M;
			}
			else
			{
				L = M;
			}
		}
		
		if(R == 1)
		{
			return OUT;
		}
		
		if(L + 1 == (int)P.size())
		{
			if(intersect(Segment(P[0],P[L]),p))
			{
				return ON;
			}
			return OUT;
		}

		if(L == 1)
		{
			if(intersect(Segment(P[0],P[L]),p))
			{
				return ON;
			}
		}

		real tri = cross(P[L] - p,P[R] - p);
		return EQ(tri,0) ? ON : tri < -EPS ? OUT : IN;
	}
}; //namespace geometry

#include<algorithm>
#include<vector>
#include<cassert>
using namespace std;
struct UnionFind
{
	private:
	int n;
	vector<int> par,siz;

	public:
	UnionFind(int n) :n(n),par(n,-1),siz(n,1) {}

	int root(int u) 
	{
		assert(0 <= u && u < n);
		return (par[u] < 0 ? u:par[u] = root(par[u]));
	}

	bool same(int u,int v)
	{
		assert(0 <= u && u < n && 0 <= v && v < n);
		return root(u) == root(v);
	}

	bool unite(int u,int v)
	{
		assert(0 <= u && u < n && 0 <= v && v < n);
		u = root(u),v = root(v);
		if(u == v) return false;

		if(siz[u] < siz[v]) swap(u,v);

		siz[u] += siz[v];
		par[v] = u;

		return true;
	}

	int size(int u)
	{
		assert(0 <= u && u < n);
		return siz[root(u)];
	}

	vector<vector<int>> components()
	{
		vector<vector<int>> ret(n);
		for(int u = 0;u < n;u++) ret[root(u)].push_back(u);

		ret.erase(remove_if(ret.begin(),ret.end(),[](vector<int> v) { return v.empty();}),ret.end());

		return ret;
	}
};

void Main()
{
	int N,M;
	cin >> N >> M;
	vector<int> A(M),B(M);
	for(int i = 0;i < M;i++)
	{
		cin >> A[i] >> B[i];
		A[i]--; B[i]--;
	}
	vector<int> C(N);
	for(int i = 0;i < N;i++)
	{
		cin >> C[i];
		C[i]--;
	}
	const int K = 10;
	vector<int> W(K);
	for(int i = 0;i < K;i++)
	{
		cin >> W[i];
	}
	int Q;
	cin >> Q;
	vector<int> U(Q),V(Q);
	vector<long long> ans(Q,(long long)1e18);
	for(int i = 0;i < Q;i++)
	{
		cin >> U[i] >> V[i];
		U[i]--; V[i]--;
	}
	for(int S = 0;S < 1 << K;S++)
	{
		UnionFind uf(N);
		long long cur = 0;
		for(int i = 0;i < K;i++)
		{
			if(S >> i & 1)
			{
				cur += W[i];
			}
		}
		for(int i = 0;i < M;i++)
		{
			if((S >> C[A[i]] & 1) && (S >> C[B[i]] & 1))
			{
				uf.unite(A[i],B[i]);
			}
		}
		for(int i = 0;i < Q;i++)
		{
			if(uf.same(U[i],V[i]))
			{
				ans[i] = min(ans[i],cur);
			}
		}
	}
	for(int i = 0;i < Q;i++)
	{
		if(ans[i] == (long long)1e18)
		{
			ans[i] = -1;
		}
		cout << ans[i] << "\n";
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt = 1;
	/* cin >> tt; */
	while(tt--) Main();
}
0