Submission #968677


Source Code Expand

#include <bits/stdc++.h>
using namespace std;


#define MAX 100002

int n;
int x;

struct st{
	int go;
	long long int cost;
	st(int go_,long long int cost_){
		go = go_;
		cost = cost_;
	}
};

vector<st> v[MAX];

bool used[MAX];

long long int ans = 0;
long long int way = 0;

vector<long long int> vv;

int cnt[MAX];

inline void dfs(int b,long long int c,int pr=-1){
	cnt[b] = 1;
	if(c<=x)vv.push_back(c);
	for (int i = 0; i < v[b].size(); i++){
		if (v[b][i].go == pr)continue;
		if (used[v[b][i].go]){
			continue;
		}
		dfs(v[b][i].go,c+v[b][i].cost,b);
		cnt[b] += cnt[v[b][i].go];
	}
}
vector<vector<long long int> > V;

vector<pair<long long int, int> > lis;

vector<vector<int> > ids;

vector<long long int> bit;
vector<int> cnt_bit;

void add(int i, long long int x){
	int MX = bit.size();
	i++;
	while (i < MX){
		bit[i] += x;
		if(x>0)cnt_bit[i] += 1;
		else cnt_bit[i] -= 1;
		i += i&-i;
	}
}
long long int sum(int i){
	long long int r = 0;
	i++;
	while (i){
		r += bit[i];
		i -= i&-i;
	}
	return r;
}
int sum_cnt(int i){
	int r = 0;
	i++;
	while (i){
		r += cnt_bit[i];
		i -= i&-i;
	}
	return r;
}
pair<int, int> find_cent(int b,int all,int pr=-1){
	pair<int, int> r = make_pair(INT_MAX, -1);
	int M = 0;
	int sub = 0;
	for (int i = 0; i < v[b].size(); i++){
		if (used[v[b][i].go] || pr == v[b][i].go)continue;
		r = min(r, find_cent(v[b][i].go, all, b));
		M = max(M, cnt[v[b][i].go]);
		sub += cnt[v[b][i].go];
	}
	M = max(M, all - sub-1);
	r = min(r, make_pair(M, b));
	return r;
}
void solve(int b){
	used[b] = true;
	V.clear();
	for (int i = 0; i < v[b].size(); i++){
		if (!used[v[b][i].go]){
			dfs(v[b][i].go, v[b][i].cost);
			way += vv.size();
			V.push_back(vv);
			vv.clear();
		}
	}
	if (V.size() == 0)return;
	lis.clear();
	ids.clear();
	ids.assign(V.size(), vector<int>());
	for (int i = 0; i < V.size(); i++){
		for (int j = 0; j < V[i].size(); j++){
			ans += V[i][j];
			lis.push_back(make_pair(V[i][j],i));
		}
	}
	bit.assign(lis.size()+1, 0);
	cnt_bit.assign(lis.size() + 1, 0);
	sort(lis.begin(), lis.end());
	for (int i = 0; i < lis.size(); i++){
		ids[lis[i].second].push_back(i);
		add(i, lis[i].first);
	}
	for (int i = 0; i < ids.size(); i++){
		for (int j = 0; j < ids[i].size(); j++){
			add(ids[i][j], -lis[ids[i][j]].first);
		}
		for (int j = 0; j < V[i].size(); j++){
			long long int eq = x - V[i][j];
			int ii = upper_bound(lis.begin(), lis.end(), make_pair(eq,INT_MAX)) - lis.begin();
			int way2 = sum_cnt(ii-1);
			ans += sum(ii-1);
			ans += (long long int)(way2)*(long long int)(V[i][j]);
			way += way2;
		}
		
	}
	for (int i = 0; i < v[b].size(); i++){
		if (used[v[b][i].go] == false){
			solve(find_cent(v[b][i].go, cnt[v[b][i].go]).second);
		}
	}
}
bool cmp(st &a, st &b){
	return a.cost < b.cost;
}
set<pair<int, int> > mp;
int main(){
	cin >> n >> x;
	for (int i = 1; i < n; i++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		a--;
		b--;
		v[a].push_back(st(b, c));
		v[b].push_back(st(a, c));
	}
	solve(0);
	memset(used, false, sizeof(used));
	for (int i = 0; i < n; i++){
		sort(v[i].begin(), v[i].end(), cmp);
	}
	for (int i = 0; i < n; i++){
		for (int j = 0; j < v[i].size(); j++){
			if (v[i][j].cost>x){
				if (mp.count(make_pair(i,v[i][j].go))==0){
					mp.insert(make_pair(i, v[i][j].go));
					mp.insert(make_pair(v[i][j].go, i));
					int go = v[i][j].go;
					long long int min_cost = INT_MAX;
					for (int kk = 0; kk < min(3,(int)v[go].size()); kk++){
						if (v[go][kk].go != i){
							min_cost = min(min_cost, v[go][kk].cost);
						}
					}
					if (j != 0){
						min_cost = min(min_cost, v[i][0].cost);
					}
					else{
						if (v[i].size() > 1){
							min_cost = min(min_cost, v[i][1].cost);
						}
					}
					if (min_cost != INT_MAX){
						min_cost += x;
					}
					long long int C = v[i][j].cost;
					C = min(C, min_cost);
					if (n>v[i].size()+v[go].size()){
						C = min(C, x * 2LL);
					}
					way++;
					ans += C;
				}
			}
		}
	}
	long long int P = (n);
	P *= (n - 1);
	P /= 2LL;
	P -= way;
	P *= x;
	ans += P;
	printf("%lld\n", ans);
	return 0;
}

Submission Info

Submission Time
Task D - 道路網
User Kmcode
Language C++14 (GCC 5.4.1)
Score 1200
Code Size 4260 Byte
Status AC
Exec Time 364 ms
Memory 25328 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:149:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);
                              ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1200 / 1200
Status
AC × 2
AC × 46
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt
All 00_example_01.txt, 00_example_02.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 20_k-ary_01.txt, 20_k-ary_02.txt, 20_k-ary_03.txt, 20_k-ary_04.txt, 20_k-ary_05.txt, 20_k-ary_06.txt, 20_k-ary_07.txt, 20_k-ary_08.txt, 20_k-ary_09.txt, 20_k-ary_10.txt, 30_star_01.txt, 30_star_02.txt, 30_star_03.txt, 30_star_04.txt, 30_star_05.txt, 40_pseudostar_01.txt, 40_pseudostar_02.txt, 40_pseudostar_04.txt, 40_pseudostar_05.txt, 40_pseudostar_06.txt, 50_line_01.txt, 50_line_02.txt, 50_line_03.txt, 60_max_01.txt, 60_max_02.txt, 60_max_03.txt, 60_max_04.txt, 70_hand_01.txt, 70_hand_02.txt, 71_hand_01.txt, 72_hand_01.txt, 80_kill2X_01.txt, 80_kill2X_02.txt, 80_kill2X_03.txt, 80_kill2X_04.txt, 80_kill2X_05.txt, 80_kill2X_06.txt, 80_kill2X_07.txt, 80_kill2X_08.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 5 ms 2688 KB
00_example_02.txt AC 5 ms 2688 KB
10_rand_01.txt AC 5 ms 2688 KB
10_rand_02.txt AC 5 ms 2688 KB
10_rand_03.txt AC 5 ms 2688 KB
10_rand_04.txt AC 5 ms 2688 KB
10_rand_05.txt AC 6 ms 2688 KB
20_k-ary_01.txt AC 332 ms 13676 KB
20_k-ary_02.txt AC 316 ms 13680 KB
20_k-ary_03.txt AC 339 ms 13680 KB
20_k-ary_04.txt AC 227 ms 14068 KB
20_k-ary_05.txt AC 185 ms 14452 KB
20_k-ary_06.txt AC 131 ms 13300 KB
20_k-ary_07.txt AC 126 ms 13936 KB
20_k-ary_08.txt AC 129 ms 13300 KB
20_k-ary_09.txt AC 125 ms 13040 KB
20_k-ary_10.txt AC 128 ms 12916 KB
30_star_01.txt AC 173 ms 21868 KB
30_star_02.txt AC 186 ms 21740 KB
30_star_03.txt AC 191 ms 21484 KB
30_star_04.txt AC 177 ms 20588 KB
30_star_05.txt AC 158 ms 20076 KB
40_pseudostar_01.txt AC 141 ms 20716 KB
40_pseudostar_02.txt AC 159 ms 20460 KB
40_pseudostar_04.txt AC 136 ms 17648 KB
40_pseudostar_05.txt AC 158 ms 17132 KB
40_pseudostar_06.txt AC 141 ms 17392 KB
50_line_01.txt AC 295 ms 20608 KB
50_line_02.txt AC 292 ms 20608 KB
50_line_03.txt AC 295 ms 20776 KB
60_max_01.txt AC 293 ms 13696 KB
60_max_02.txt AC 320 ms 13684 KB
60_max_03.txt AC 261 ms 13800 KB
60_max_04.txt AC 283 ms 13684 KB
70_hand_01.txt AC 5 ms 2688 KB
70_hand_02.txt AC 5 ms 2688 KB
71_hand_01.txt AC 144 ms 8192 KB
72_hand_01.txt AC 364 ms 25328 KB
80_kill2X_01.txt AC 176 ms 21868 KB
80_kill2X_02.txt AC 189 ms 21868 KB
80_kill2X_03.txt AC 187 ms 21868 KB
80_kill2X_04.txt AC 196 ms 21996 KB
80_kill2X_05.txt AC 168 ms 20204 KB
80_kill2X_06.txt AC 167 ms 20080 KB
80_kill2X_07.txt AC 160 ms 19824 KB
80_kill2X_08.txt AC 148 ms 20208 KB