Submission #1293813


Source Code Expand

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
 
 
 
 
#ifdef NO_UNLOCK_IO
#define getchar_unlocked getchar
#define putchar_unlocked putchar
#endif
struct FastIO {
	static void scan(double &x) {
		scanf("%lf", &x);
	}
	template <class Integral>
	static void scan(Integral &x) {
		int k, m = 1;
		x = 0;
		for (;;) {
			k = getchar_unlocked();
			//if (k == '-') {
			//	m = -1;
			//	break;
			//}
			//else
			if ('0' <= k && k <= '9') {
				x = k - '0';
				break;
			}
		}
		for (;;) {
			k = getchar_unlocked();
			if (k < '0' || k > '9')
				break;
 
			x = x * 10 + k - '0';
		}
		//x *= m;//mul is faster than branch-misprediction penalty (maybe)
	}
	template <class Arithmetic, class... Rest>
	static void scan(Arithmetic &x, Rest&... y) {
		scan(x);
		scan(y...);
	}
	static void print(double x, char c) {
		printf("%.12f%c", x, c);
	}
	static void print(const char *x, char c) {
		printf("%s%c", x, c);
	}
	template <class Integral>
	static void print(Integral x, char c) {
		int s = 0, m = 0;
		char f[20];//Is this faster than "static char" ?
		if (x < 0) {
			m = 1;
			x = -x;
		}
		while (x) {
			f[s++] = x % 10;
			x /= 10;
		}
 
		if (!s)
			f[s++] = 0;
 
		if (m) putchar_unlocked('-');
		while (s--)
			putchar_unlocked(f[s] + '0');
 
		putchar_unlocked(c);
	}
	template <class Arithmetic>
	static void println(Arithmetic x) {
		print(x, '\n');
	}
};
 
 
 
#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
typedef deque<bool> db;
template<class T> using vv = vector<vector< T > >;
 
// cout vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
	int len = v.size(); s << "\n";
	for (int i = 0; i < len; ++i) {
		s << v[i]; if (i < len - 1) s << "\t";
	}
	s << "\n"; return s;
}
 
// cout 2-dimentional vector
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
	int len = vv.size();
	for (int i = 0; i < len; ++i) { s << vv[i]; }
	return s;
}
 
 
class UF {
private:
	vector<int> par; // parent
	vector<int> sizes;
	void init(int n) {
		par.resize(n);
		for (int i = 0; i < n; ++i) {
			par[i] = i;
		}
		sizes.assign(n, 1);
	}
 
	void clear() {
		par.clear();
		sizes.clear();
	}
 
public:
	UF() {}
	UF(int n) {
		init(n);
	}
 
	void assign(int n) {
		clear();
		init(n);
	}
 
	int root(int x) {
		if (x == par[x]) {
			return x;
		}
		return par[x] = root(par[x]);
	}
 
	void unite(int x, int y) {
		x = root(x);
		y = root(y);
		if (x == y) {
			return;
		}
		if (sizes[x] < sizes[y]) {
			swap(x, y);
		}
		par[y] = x;
		sizes[x] += sizes[y];
		sizes[y] = 0;
	}
 
	bool same(int x, int y) {
		return root(x) == root(y);
	}
 
	int size(int x) {
		return sizes[root(x)];
	}
};
 
int a, t, k;
vi n;
vector<set<int> > cities_including;
vector<set<int> > towns_included_by;
 
vector<vvi> edges_included_by;
int m;
 
int common_city(int town1, int town2) {
	if (cities_including[town1].size() > cities_including[town2].size()) {
		swap(town1, town2);
	}
	for (int city : cities_including[town1]) {
		if (cities_including[town2].find(city) != cities_including[town2].end()) {
			return city;
		}
	}
	assert(false);
	return -1;
}
 
int num_edges;
int num_towns;
vi costs;
map<int, int> town_id;
vvi g;
 
void dfs(int city, int edge_index, int used_edges, int cost_sum, UF uf) {
	if (edge_index < num_edges - 1) {
		dfs(city, edge_index + 1, used_edges, cost_sum, uf);
	}
	if (!(uf.same(g[edge_index][0], g[edge_index][1]))) {
		uf.unite(g[edge_index][0], g[edge_index][1]);
		cost_sum += g[edge_index][2];
		edge_index += 1;
		used_edges += 1;
		if (used_edges == num_towns - 1) {
			costs.push_back(cost_sum);
			return;
		}
		if (edge_index == num_edges) {
			return;
		}
		dfs(city, edge_index, used_edges, cost_sum, uf);
	}
}
 
void dfs_main(int city) {
	num_edges = (int)edges_included_by[city].size();
	num_towns = (int)towns_included_by[city].size();
	costs.clear();
	//  costs.reserve(HOGE);
	UF uf;
	uf.assign(num_towns);
	town_id.clear();
	for (int town : towns_included_by[city]) {
		town_id[town] = (int)town_id.size();
	}
	g.clear();
	for (vi edge : edges_included_by[city]) {
		int u = town_id[edge[0]];
		int v = town_id[edge[1]];
		g.push_back({ u, v, edge[2] });
	}
 
	dfs(city, 0, 0, 0, uf);
}
 
ll INF = 1e13;
 
int main() {
	FastIO::scan(a);
  FastIO::scan(t);
  FastIO::scan(k);
	n.resize(a);
	cities_including.resize(t);
	towns_included_by.resize(a);
	rep(i, a) { // city number
		FastIO::scan(n[i]);
		rep(j, n[i]) {
			int town;
			FastIO::scan(town);
			town -= 1;
			cities_including[town].insert(i);
			towns_included_by[i].insert(town);
		}
	}
 
	int sum_all_edges = 0;
	edges_included_by.resize(a);
	FastIO::scan(m);
	rep(i, m) {
		int town1, town2, cost;
		FastIO::scan(town1);
    FastIO::scan(town2);
    FastIO::scan(cost);
		town1 -= 1;
		town2 -= 1;
		int city = common_city(town1, town2);
		if (town1 > town2) { swap(town1, town2); }
		edges_included_by[city].push_back({ town1, town2, cost });
		sum_all_edges += cost;
	}
 
	vvi costs_of_city(a, vi(77 * 6 + 1, 0)); // Max(cost_i) * (7C2 - 6)
	ll judge = 1;
	rep(i, a) {
		int sum_costs = 0;
		for (auto e : edges_included_by[i]) {
			sum_costs += e[2];
		}
 
		dfs_main(i);
		//    assert((int)costs.size() > 0);
		judge *= (int)costs.size(); // costs is the list of spanning trees
		judge = min(judge, INF);
		rep(j, (int)costs.size()) {
			//      int cost = sum_costs - costs[j];
			//      costs_of_city[i][cost] += 1;
			costs_of_city[i][costs[j]] += 1;
		}
	}
	if (judge < k) {
		printf("-1\n");
		return 0;
	}
 
	vll dp(77 * 6 * 77 + 1, 0); // Max(cost_i) * (7 - 1) * A
	dp[0] = 1;
	rep(i, a) {
		vll ndp(77 * 6 * 77 + 1, 0);
		rep(j, 77 * 6 + 1) {
			if (costs_of_city[i][j] == 0) {
				continue;
			}
			rep(ii, 77 * 6 * 77 + 1) {
				if (dp[ii] == 0) {
					continue;
				}
				ndp[j + ii] += min(INF, dp[ii]) * costs_of_city[i][j];
			}
		}
		swap(dp, ndp);
	}
 
	vector<pair<int, ll> > ans;
	ans.reserve((int)dp.size());
 
	rep(i, 77 * 6 * 77 + 1) {
		if (dp[i] == 0) {
			continue;
		}
		ans.push_back(make_pair(sum_all_edges - i, dp[i]));
	}
	sort(all(ans));
 
	ll k_ = k;
	for (auto p : ans) {
		k_ -= p.second;
		if (k_ <= 0) {
			printf("%d\n", p.first);
			return 0;
		}
	}
 
	return 0;
}

Submission Info

Submission Time
Task D - 覚醒ノ高橋君
User eukaryo
Language C++14 (GCC 5.4.1)
Score 0
Code Size 7179 Byte
Status RE
Exec Time 283 ms
Memory 262400 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 5
WA × 27
RE × 31
Set Name Test Cases
All 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_randt_00.txt, 01_randt_01.txt, 01_randt_02.txt, 01_randt_03.txt, 01_randt_04.txt, 01_randt_05.txt, 01_randt_06.txt, 01_randt_07.txt, 01_randt_08.txt, 01_randt_09.txt, 01_randt_10.txt, 01_randt_11.txt, 01_randt_12.txt, 01_randt_13.txt, 01_randt_14.txt, 01_randt_15.txt, 01_randt_16.txt, 01_randt_17.txt, 01_randt_18.txt, 01_randt_19.txt, 01_randt_20.txt, 01_randt_21.txt, 01_randt_22.txt, 01_randt_23.txt, 01_randt_24.txt, 01_randt_25.txt, 01_randt_26.txt, 01_randt_27.txt, 01_randt_28.txt, 01_randt_29.txt, 02_maxrandt_00.txt, 02_maxrandt_01.txt, 02_maxrandt_02.txt, 02_maxrandt_03.txt, 02_maxrandt_04.txt, 02_maxrandt_05.txt, 02_maxrandt_06.txt, 02_maxrandt_07.txt, 02_maxrandt_08.txt, 02_maxrandt_09.txt, 02_maxrandt_10.txt, 02_maxrandt_11.txt, 02_maxrandt_12.txt, 02_maxrandt_13.txt, 02_maxrandt_14.txt, 02_maxrandt_15.txt, 02_maxrandt_16.txt, 02_maxrandt_17.txt, 02_maxrandt_18.txt, 02_maxrandt_19.txt, 03_overflow_00.txt, 03_overflow_01.txt, 03_overflow_02.txt, 03_overflow_03.txt, 03_overflow_04.txt, 03_overflow_05.txt, 03_overflow_06.txt, 03_overflow_07.txt, 03_overflow_08.txt, 03_overflow_09.txt
Case Name Status Exec Time Memory
00_sample_01.txt RE 102 ms 256 KB
00_sample_02.txt AC 1 ms 256 KB
00_sample_03.txt RE 101 ms 256 KB
01_randt_00.txt RE 102 ms 384 KB
01_randt_01.txt RE 102 ms 384 KB
01_randt_02.txt RE 102 ms 384 KB
01_randt_03.txt AC 2 ms 768 KB
01_randt_04.txt RE 102 ms 384 KB
01_randt_05.txt AC 1 ms 256 KB
01_randt_06.txt RE 102 ms 256 KB
01_randt_07.txt RE 102 ms 256 KB
01_randt_08.txt RE 102 ms 256 KB
01_randt_09.txt RE 102 ms 384 KB
01_randt_10.txt RE 101 ms 512 KB
01_randt_11.txt RE 103 ms 256 KB
01_randt_12.txt RE 102 ms 256 KB
01_randt_13.txt RE 101 ms 256 KB
01_randt_14.txt RE 101 ms 256 KB
01_randt_15.txt RE 102 ms 512 KB
01_randt_16.txt RE 101 ms 256 KB
01_randt_17.txt RE 102 ms 256 KB
01_randt_18.txt AC 1 ms 256 KB
01_randt_19.txt RE 101 ms 384 KB
01_randt_20.txt RE 100 ms 256 KB
01_randt_21.txt RE 101 ms 256 KB
01_randt_22.txt RE 101 ms 384 KB
01_randt_23.txt AC 1 ms 256 KB
01_randt_24.txt RE 103 ms 256 KB
01_randt_25.txt RE 101 ms 256 KB
01_randt_26.txt RE 102 ms 256 KB
01_randt_27.txt RE 104 ms 512 KB
01_randt_28.txt RE 283 ms 262400 KB
01_randt_29.txt RE 102 ms 384 KB
02_maxrandt_00.txt WA 9 ms 512 KB
02_maxrandt_01.txt WA 22 ms 512 KB
02_maxrandt_02.txt RE 104 ms 640 KB
02_maxrandt_03.txt WA 16 ms 512 KB
02_maxrandt_04.txt WA 3 ms 512 KB
02_maxrandt_05.txt RE 103 ms 512 KB
02_maxrandt_06.txt WA 4 ms 512 KB
02_maxrandt_07.txt WA 3 ms 512 KB
02_maxrandt_08.txt WA 27 ms 512 KB
02_maxrandt_09.txt WA 62 ms 640 KB
02_maxrandt_10.txt WA 32 ms 512 KB
02_maxrandt_11.txt WA 12 ms 512 KB
02_maxrandt_12.txt WA 52 ms 640 KB
02_maxrandt_13.txt WA 4 ms 512 KB
02_maxrandt_14.txt WA 4 ms 512 KB
02_maxrandt_15.txt WA 24 ms 512 KB
02_maxrandt_16.txt WA 7 ms 512 KB
02_maxrandt_17.txt WA 4 ms 512 KB
02_maxrandt_18.txt WA 63 ms 640 KB
02_maxrandt_19.txt WA 40 ms 512 KB
03_overflow_00.txt WA 4 ms 512 KB
03_overflow_01.txt RE 103 ms 512 KB
03_overflow_02.txt WA 11 ms 512 KB
03_overflow_03.txt WA 107 ms 640 KB
03_overflow_04.txt WA 34 ms 512 KB
03_overflow_05.txt WA 4 ms 512 KB
03_overflow_06.txt WA 44 ms 512 KB
03_overflow_07.txt WA 25 ms 512 KB
03_overflow_08.txt WA 4 ms 512 KB
03_overflow_09.txt WA 6 ms 512 KB