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); ^