Submission #3194517
Source Code Expand
#define _GLIBCXX_DEBUG #include <bits/stdc++.h> #define ll long long #define REP(i, n) for (ll (i) = 0; (i) < (n); (i)++) #define REPI(i, a, b) for (ll (i) = (a); (i) < (b); (i)++) #define int long long #define MOD 1000000007 using namespace std; using P = pair<int, int>; using VI = vector<int>; using VVI = vector<VI>; using VVVI = vector<VVI>; class UnionFind { public: VI par, rank; UnionFind(int n) { par = VI(n); iota(par.begin(), par.end(), 0); rank = VI(n, 0); } int root(int x) { if (par[x] == x) { return x; } else { return par[x] = root(par[x]); } } void unite(int x, int y) { x = root(x); y = root(y); if (x == y) { return; } if (rank[x] < rank[y]) { par[x] = y; } else { par[y] = x; if (rank[x] == rank[y]) { rank[x]++; } } } bool same(int x, int y) { return root(x) == root(y); } }; struct edge { int u, v, cost; }; bool comp(const edge& e1, const edge& e2) { return e1.cost < e2.cost; } struct neigh { int to, cost; }; vector<vector<neigh>> g; vector<edge> es2; int kruskal(int V, vector<edge>& es) { sort(es.begin(), es.end(), comp); UnionFind uf(V); int ans = 0; for (edge e: es) { if (uf.same(e.u, e.v)) { es2.push_back(e); continue; } uf.unite(e.u, e.v); ans += e.cost; g[e.u].push_back({e.v, e.cost}); g[e.v].push_back({e.u, e.cost}); } return ans; } vector<bool> visited; int dfs(int v1, int v2, int acc) { if (v1 == v2) { return acc; } visited[v1] = true; int ans = -1; for (neigh nei: g[v1]) { if (visited[nei.to]) { continue; } ans = max(ans, dfs(nei.to, v2, max(acc, nei.cost))); } return ans; } int pow_mod(int x) { if (x == 0) { return 1; } int tmp = pow_mod(x / 2); return tmp * tmp % MOD * (x % 2 ? 2 : 1) % MOD; } signed main() { int N, M, X; cin >> N >> M >> X; vector<edge> es(M); g = vector<vector<neigh>>(N); REP (i, M) { cin >> es[i].u >> es[i].v >> es[i].cost; es[i].u--; es[i].v--; } int S = kruskal(N, es); int D = X - S; if (D < 0) { cout << 0 << endl; return 0; } int eqs = 0; int ups = 0; int lws = 0; for (edge e: es2) { visited = vector<bool>(N, false); int path = dfs(e.u, e.v, 0); assert(path <= e.cost); if (e.cost == path + D) { eqs++; } else if (e.cost > path + D) { ups++; } else { lws++; } } assert(eqs + ups + lws == es2.size()); int tmp = 2 * (pow_mod(eqs) - 1) % MOD * pow_mod(ups) % MOD; if (D == 0) { cout << ((pow_mod(N-1) - 2) % MOD * pow_mod(M-N+1) % MOD + tmp) % MOD << endl; } else { cout << tmp << endl; } }
Submission Info
Submission Time | |
---|---|
Task | E - Bichrome Spanning Tree |
User | knshnb |
Language | C++14 (GCC 5.4.1) |
Score | 900 |
Code Size | 2717 Byte |
Status | AC |
Exec Time | 165 ms |
Memory | 1280 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 900 / 900 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt |
All | 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01.txt | AC | 156 ms | 512 KB |
02.txt | AC | 156 ms | 512 KB |
03.txt | AC | 145 ms | 512 KB |
04.txt | AC | 135 ms | 896 KB |
05.txt | AC | 114 ms | 1280 KB |
06.txt | AC | 156 ms | 512 KB |
07.txt | AC | 132 ms | 896 KB |
08.txt | AC | 155 ms | 512 KB |
09.txt | AC | 132 ms | 896 KB |
10.txt | AC | 114 ms | 1280 KB |
11.txt | AC | 145 ms | 512 KB |
12.txt | AC | 4 ms | 640 KB |
13.txt | AC | 4 ms | 768 KB |
14.txt | AC | 4 ms | 384 KB |
15.txt | AC | 147 ms | 512 KB |
16.txt | AC | 7 ms | 512 KB |
17.txt | AC | 155 ms | 512 KB |
18.txt | AC | 6 ms | 512 KB |
19.txt | AC | 130 ms | 1152 KB |
20.txt | AC | 6 ms | 512 KB |
21.txt | AC | 154 ms | 640 KB |
22.txt | AC | 128 ms | 1024 KB |
23.txt | AC | 132 ms | 896 KB |
24.txt | AC | 4 ms | 640 KB |
25.txt | AC | 4 ms | 384 KB |
26.txt | AC | 141 ms | 512 KB |
27.txt | AC | 165 ms | 512 KB |
28.txt | AC | 156 ms | 640 KB |
29.txt | AC | 149 ms | 768 KB |
30.txt | AC | 152 ms | 640 KB |
31.txt | AC | 135 ms | 896 KB |
32.txt | AC | 155 ms | 640 KB |
33.txt | AC | 149 ms | 512 KB |
34.txt | AC | 144 ms | 512 KB |
35.txt | AC | 28 ms | 384 KB |
36.txt | AC | 26 ms | 384 KB |
37.txt | AC | 26 ms | 384 KB |
38.txt | AC | 155 ms | 512 KB |
39.txt | AC | 144 ms | 768 KB |
40.txt | AC | 144 ms | 768 KB |
41.txt | AC | 145 ms | 512 KB |
42.txt | AC | 33 ms | 384 KB |
43.txt | AC | 12 ms | 512 KB |
44.txt | AC | 4 ms | 384 KB |
45.txt | AC | 32 ms | 768 KB |
46.txt | AC | 69 ms | 896 KB |
47.txt | AC | 6 ms | 768 KB |
48.txt | AC | 7 ms | 384 KB |
sample-01.txt | AC | 1 ms | 256 KB |
sample-02.txt | AC | 1 ms | 256 KB |
sample-03.txt | AC | 1 ms | 256 KB |
sample-04.txt | AC | 1 ms | 256 KB |