Submission #3712504


Source Code Expand

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define MOD 1000000007

//define
ll X;
int n, m;
struct Data{
	int x, y, v;
	bool operator<(const Data a)const{
		return v < a.v;
	}
}d[2333];

void input(){
	scanf("%d %d", &n, &m);
	scanf("%lld", &X);
	for(int i = 1; i <= m; i++)
		scanf("%d %d %d", &d[i].x, &d[i].y, &d[i].v);
	std::sort(d + 1, d + m + 1);
}

//work
ll ans;
int fa[1111];
int ls, mr, eq;

int find(int a){
	if(fa[a] == a) return a;
	return fa[a] = find(fa[a]);
}

void Kruskal(int a){
	ans = 0;
	for(int i = 1; i <= n; i++) fa[i] = i;
	ans = ans + d[a].v;
	fa[d[a].x] = d[a].y;
	for(int i = 1; i <= m; i++){
		if(i == a) continue;
		int u = d[i].x, v = d[i].y;
		if(find(u) == find(v)) continue;
		fa[find(u)] = find(v);
		ans = ans + d[i].v;
	}
	if(ans < X) ls++;
	if(ans == X) eq++;
	if(ans > X) mr++;
}

int p[1111];
int Ans;
void work(){
	p[0] = 1;
	for(int i = 1; i <= n; i++)
		p[i] = p[i - 1] * 2 % MOD;
	for(int i = 1; i <= m; i++) Kruskal(i);
	if(eq == 0) for(int i = 1; i <= 1000000000) puts("0");
	else if(ls == 0)
		printf("%lld\n", 1ll * ((p[eq] - 2 + MOD) % MOD) * p[mr] % MOD);
	else
		printf("%lld\n", 1ll * 2 * ((p[eq] - 1 + MOD) % MOD) * p[mr] % MOD);
}

int main(){
	input();
	work();
	return 0;
}

Submission Info

Submission Time
Task E - Bichrome Spanning Tree
User Trestrals
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1334 Byte
Status CE

Compile Error

./Main.cpp: In function ‘void work()’:
./Main.cpp:59:44: error: expected ‘;’ before ‘)’ token
  if(eq == 0) for(int i = 1; i <= 1000000000) puts("0");
                                            ^
./Main.cpp: In function ‘void input()’:
./Main.cpp:18:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
./Main.cpp:19:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &X);
                   ^
./Main.cpp:21:47: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &d[i].x, &d[i].y, &d[i].v);
                                               ^