Submission #3712724
Source Code Expand
#if 0
cat <<EOF >mistaken-paste
#endif
// thanks for @rsk0315_h4x
#pragma GCC diagnostic ignored "-Wincompatible-pointer-types"
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
#include <time.h>
#define BIG 2000000007
#define VERYBIG 2000000000000007LL
#define MOD 1000000007
#define FOD 998244353
typedef uint64_t ull;
typedef int64_t sll;
#define N_MAX 1000000
#ifdef __cplusplus
#include <queue>
#include <stack>
#include <tuple>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <functional>
#include <array>
using std::queue;
using std::priority_queue;
using std::stack;
using std::tuple;
using std::set;
using std::map;
using std::vector;
using std::greater;
using std::pair;
using std::string;
using std::get;
template <typename T, typename U>
pair<T, U> operator+(pair<T, U> l, pair<T, U> r) {
return pair<T, U>(l.first + r.first, l.second + r.second);
}
#endif
typedef struct {
int32_t a;
int32_t b;
} hw;
typedef struct {
sll a;
sll b;
} hwll;
typedef struct {
sll a;
sll b;
sll c;
} hwllc;
typedef struct {
hwll a;
hwll b;
} linell;
ull n, m;
ull h, w;
ull k;
ull q;
sll va, vb, vc, vd, ve, vf;
ull ua, ub, uc, ud, ue, uf;
long double vra, vrb, vrc;
double vda, vdb, vdc;
char ch, dh;
ull umin (ull x, ull y) {
return (x < y) ? x : y;
}
ull umax (ull x, ull y) {
return (x > y) ? x : y;
}
sll smin (sll x, sll y) {
return (x < y) ? x : y;
}
sll smax (sll x, sll y) {
return (x > y) ? x : y;
}
ull gcd (ull x, ull y) {
if (x < y) {
return gcd(y, x);
} else if (y == 0) {
return x;
} else {
return gcd(y, x % y);
}
}
ull bitpow (ull a, ull x, ull modulo) {
ull result = 1;
while (x) {
if (x & 1) {
result *= a;
result %= modulo;
}
x /= 2;
a = (a * a) % modulo;
}
return result;
}
ull divide (ull a, ull b, ull modulo) {
return (a * bitpow(b, modulo - 2, modulo)) % modulo;
}
ull udiff (ull a, ull b) {
if (a >= b) {
return a - b;
} else {
return b - a;
}
}
sll sdiff (sll a, sll b) {
if (a >= b) {
return a - b;
} else {
return b - a;
}
}
int bitcount (ull n) {
int result = 0;
while (n) {
if (n & 1) result++;
n /= 2;
}
return result;
}
#define BEGCMP(NAME) int32_t NAME (const void *left, const void *right)
#define DEFLR(TYPE) TYPE l=*(TYPE*)left,r=*(TYPE*)right
#define CMPRET(L, R) if((L)<(R))return-1;if((L)>(R))return+1
// int32_t pullcomp (const void *left, const void *right) {
// ull l = *(ull*)left;
// ull r = *(ull*)right;
// if (l < r) {
// return -1;
// }
// if (l > r) {
// return +1;
// }
// return 0;
// }
BEGCMP(pullcomp){
DEFLR(ull);
CMPRET(l, r);
return 0;
}
BEGCMP(prevcomp){
DEFLR(ull);
CMPRET(r, l);
return 0;
}
BEGCMP(psllcomp){
DEFLR(sll);
CMPRET(l, r);
return 0;
}
BEGCMP(pcharcomp){
DEFLR(char);
CMPRET(l, r);
return 0;
}
BEGCMP(pdoublecomp){
DEFLR(double);
CMPRET(l, r);
return 0;
}
int32_t pstrcomp (const void *left, const void *right) {
char* l = *(char**)left;
char* r = *(char**)right;
return strcmp(l, r);
}
BEGCMP(phwllABcomp){
DEFLR(hwll);
CMPRET(l.a, r.a);
CMPRET(l.b, r.b);
return 0;
}
BEGCMP(phwllREVcomp){
DEFLR(hwll);
CMPRET(l.b, r.b);
CMPRET(l.a, r.a);
return 0;
}
BEGCMP(ptriplecomp){
DEFLR(hwllc);
CMPRET(l.a, r.a);
CMPRET(l.b, r.b);
CMPRET(l.c, r.c);
return 0;
}
BEGCMP(ptripleREVcomp){
DEFLR(hwllc);
CMPRET(l.b, r.b);
CMPRET(l.a, r.a);
CMPRET(l.c, r.c);
return 0;
}
int32_t pquadcomp (const void *left, const void *right) {
linell l = *(linell*)left;
linell r = *(linell*)right;
sll ac = phwllABcomp(&(l.a), &(r.a));
if (ac) return ac;
sll bc = phwllABcomp(&(l.b), &(r.b));
if (bc) return bc;
return 0;
}
bool isinrange (sll left, sll x, sll right) {
return (left <= x && x <= right);
}
bool isinrange_soft (sll left, sll x, sll right) {
return (left <= x && x <= right) || (left >= x && x >= right);
}
sll a[N_MAX + 5];
// ull a[N_MAX];
// sll a[3001][3001];
sll b[N_MAX + 5];
// sll b[3001][3001];
sll c[N_MAX + 5];
sll d[N_MAX + 5];
sll e[N_MAX];
// char s[N_MAX + 1];
char s[3010][3010];
char t[N_MAX + 1];
// char t[3010][3010];
// char u[N_MAX + 1];
hwll xy[N_MAX];
hwllc tup[N_MAX];
sll table[3000][3000];
// here we go
hwllc g[N_MAX];
ull gin[N_MAX];
bool isgood[N_MAX];
ull parent[N_MAX], size[N_MAX];
void uf_init (ull n) {
for (sll i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
ull uf_find (ull x) {
if (parent[x] == x) return x;
return parent[x] = uf_find(parent[x]);
}
bool uf_union (ull a, ull b) {
a = uf_find(a);
b = uf_find(b);
if (a == b) return false;
if (size[a] < size[b]) {
a ^= b;
b ^= a;
a ^= b;
}
parent[b] = a;
size[a] += size[b];
return true;
}
ull depth[N_MAX];
ull dpar[20][N_MAX];
ull dcos[20][N_MAX];
void dfs (ull v, ull p) {
for (sll i = gin[v]; i < gin[v + 1]; i++) {
ull u = g[i].b;
if (u == p) continue;
depth[u] = depth[v] + 1;
dpar[0][u] = v;
dcos[0][u] = g[i].c;
// printf("%llu: dep%llu par%llu cos%llu\n", v, depth[u], dpar[0][u], dcos[0][u]);
dfs(u, v);
}
}
ull maxcost (ull v, ull u) {
ull r = 0;
sll i, j;
if (depth[v] > depth[u]) {
v ^= u;
u ^= v;
v ^= u;
}
ull dif = depth[u] - depth[v];
if (dif) for (i = 19; i >= 0; i--) {
if (dif & (1LL << i)) {
r = umax(r, dcos[i][u]);
u = dpar[i][u];
}
}
if (v == u) return r;
for (i = 19; i >= 0; i--) {
if (dpar[i][v] != dpar[i][u]) {
r = umax(r, umax(dcos[i][v], dcos[i][u]));
v = dpar[i][v];
u = dpar[i][u];
}
}
r = umax(r, umax(dcos[0][v], dcos[0][u]));
return r;
}
ull solve () {
sll i, j, ki, li;
ull result = 0;
// sll result = 0;
double dresult = 0;
// ull maybe = 0;
sll maybe = 0;
// ull sum = 0;
sll sum = 0;
sll item;
ull *dpcell;
for (i = 0; i < m; i++) {
xy[i] = (hwll){c[i], i};
}
qsort(xy, m, sizeof(hwll), phwllABcomp);
ull amin = 0;
uf_init(n);
for (i = 0; i < m; i++) {
ull x = xy[i].b;
if (uf_find(a[x]) == uf_find(b[x])) continue;
isgood[x] = true;
amin += xy[i].a;
uf_union(a[x], b[x]);
}
// printf("amin; %llu\n", amin);
// for (i = 0; i < m; i++) {
// if (isgood[i]) {
// printf("%llu-%llu: %llu\n", a[i], b[i], c[i]);
// }
// }
if (amin > k) goto fail;
if (amin == k) {
result += ((bitpow(2, n - 1, MOD) + MOD - 2) % MOD) * bitpow(2, m - (n - 1), MOD) % MOD;
}
ull cnt = 1;
ull remain = m - (n - 1);
j = 0;
for (i = 0; i < m; i++) {
if (!isgood[i]) continue;
g[j * 2] = (hwllc){a[i], b[i], c[i]};
g[j * 2 + 1] = (hwllc){b[i], a[i], c[i]};
j++;
}
qsort(g, (n - 1) * 2, sizeof(hwllc), ptriplecomp);
i = j = 0;
while (i <= n) {
gin[i] = j;
while (j < (n - 1) * 2 && g[j].a == i) j++;
i++;
}
dfs(0, n);
for (i = 1; i < 20; i++) {
for (j = 0; j < n; j++) {
ull p = dpar[i - 1][j];
dpar[i][j] = dpar[i - 1][p];
dcos[i][j] = umax(dcos[i - 1][j], dcos[i - 1][p]);
}
}
j = 0;
for (i = 0; i < m; i++) {
if (isgood[i]) continue;
ull mcos = maxcost(a[i], b[i]);
ull newmin = amin - mcos + c[i];
xy[j++] = (hwll){newmin, i};
}
qsort(xy, j, sizeof(hwll), phwllABcomp);
// printf("%llu..\n", result);
for (i = 0; i < m; i++) {
ull x = xy[i].b;
if (isgood[x]) continue;
remain--;
// ull mcos = maxcost(a[x], b[x]);
// ull newmin = amin - mcos + c[x];
ull newmin = xy[i].a;
// printf("%llu--%llu: %llu\n", a[x], b[x], mcos);
if (newmin < k) {
//
} else if (newmin == k) {
result += bitpow(2, cnt + remain, MOD);
result %= MOD;
// printf("%llu\n", result);
} else {
cnt++;
}
}
printf("%lld\n", result);
// printf("%.15lf\n", dresult);
// puts(s);
return 0;
success:
// puts("YES");
puts("Yes");
// printf("%llu\n", result);
// puts("0");
// puts("Yay!");
return 0;
fail:
// puts("NO");
// puts("No");
puts("0");
// puts("-1");
// puts("-1 -1 -1");
// puts("invalid");
return 1;
}
int32_t main (void) {
int32_t i, j;
int32_t x, y;
// scanf("%llu%llu", &h, &w);
scanf("%llu%llu", &n, &m);
scanf("%llu", &k, &n, &m);
// scanf("%llu%llu", &h, &w);
// scanf("%llu", &q);
// scanf("%s", s);
// scanf("%lld%lld", &va, &vb, &vc, &vd);
// scanf("%llu%llu%llu", &ua, &ub, &uc, &ud);
// scanf("%s", t);
// scanf("%lld", &m);
for (i = 0; i < m; i++) {
// scanf("%lld%lld", &xy[i].a, &xy[i].b);
// scanf("%lld%lld%lld", &tup[i].a, &tup[i].b, &tup[i].c);
scanf("%lld", &a[i]);
scanf("%lld", &b[i]);
scanf("%lld", &c[i]);
// scanf("%lld", &d[i]);
a[i]--;
b[i]--;
// c[i]--;
// d[i]--;
// tup[i].a--;
// tup[i].b--;
}
// scanf("%llu", &m, &k);
// scanf("%llu", &q);
// scanf("%s", s);
// for (i = 0; i < n; i++) {
// scanf("%lld", &b[i]);
// b[i]--;
// }
// scanf("%llu", &q);
// for (i = 0; i < h; i++) {
// for (j = 0; j < w; j++) {
// scanf("%lld", &table[i][j]);
// table[i][j]--;
// }
// }
// for (i = 0; i < h; i++) {
// scanf("%s", s[i]);
// }
solve();
return 0;
}
Submission Info
Submission Time
2018-12-03 21:31:41+0900
Task
E - Bichrome Spanning Tree
User
sheyasutaka
Language
C (GCC 5.4.1)
Score
900
Code Size
9454 Byte
Status
AC
Exec Time
30 ms
Memory
104700 KB
Compile Error
./Main.c: In function ‘solve’:
./Main.c:448:9: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘ull {aka long unsigned int}’ [-Wformat=]
printf("%lld\n", result);
^
./Main.c: In function ‘main’:
./Main.c:479:8: warning: format ‘%llu’ expects argument of type ‘long long unsigned int *’, but argument 2 has type ‘ull * {aka long unsigned int *}’ [-Wformat=]
scanf("%llu%llu", &n, &m);
^
./Main.c:479:8: warning: format ‘%llu’ expects argument of type ‘long long unsigned int *’, but argument 3 has type ‘ull * {aka long unsigned int *}’ [-Wformat=]
./Main.c:480:8: warning: format ‘%llu’ expects argument of type ‘long long unsigned int *’, but argument 2 has type ‘ull * {aka long unsigned int *}’ [-Wformat=]
scanf("%llu", &k, &n, &m);
^
./Main.c:480:8: warning: too many arguments for format [-Wformat-extra-args]
./Main.c:491:9: warning: format ‘%lld’ expects argument of type ‘long long int *’, but argument 2 has type ‘sll * {aka long int *}’ [...
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
30 ms
104700 KB
02.txt
AC
29 ms
104700 KB
03.txt
AC
29 ms
104700 KB
04.txt
AC
29 ms
104700 KB
05.txt
AC
29 ms
104700 KB
06.txt
AC
29 ms
104700 KB
07.txt
AC
29 ms
104700 KB
08.txt
AC
29 ms
104700 KB
09.txt
AC
29 ms
104700 KB
10.txt
AC
29 ms
104700 KB
11.txt
AC
29 ms
104700 KB
12.txt
AC
28 ms
104700 KB
13.txt
AC
28 ms
104700 KB
14.txt
AC
28 ms
104700 KB
15.txt
AC
29 ms
104700 KB
16.txt
AC
6 ms
18684 KB
17.txt
AC
29 ms
104700 KB
18.txt
AC
6 ms
18684 KB
19.txt
AC
29 ms
104700 KB
20.txt
AC
6 ms
18684 KB
21.txt
AC
29 ms
104700 KB
22.txt
AC
29 ms
104700 KB
23.txt
AC
29 ms
104700 KB
24.txt
AC
29 ms
104700 KB
25.txt
AC
28 ms
104700 KB
26.txt
AC
29 ms
104700 KB
27.txt
AC
29 ms
104700 KB
28.txt
AC
29 ms
104700 KB
29.txt
AC
29 ms
104700 KB
30.txt
AC
29 ms
104700 KB
31.txt
AC
29 ms
104700 KB
32.txt
AC
29 ms
104700 KB
33.txt
AC
29 ms
104700 KB
34.txt
AC
29 ms
104700 KB
35.txt
AC
29 ms
104700 KB
36.txt
AC
29 ms
104700 KB
37.txt
AC
28 ms
104700 KB
38.txt
AC
29 ms
104700 KB
39.txt
AC
29 ms
104700 KB
40.txt
AC
29 ms
104700 KB
41.txt
AC
29 ms
104700 KB
42.txt
AC
29 ms
104700 KB
43.txt
AC
28 ms
104700 KB
44.txt
AC
6 ms
18556 KB
45.txt
AC
28 ms
104700 KB
46.txt
AC
29 ms
104700 KB
47.txt
AC
28 ms
104700 KB
48.txt
AC
29 ms
104700 KB
sample-01.txt
AC
28 ms
104576 KB
sample-02.txt
AC
27 ms
104576 KB
sample-03.txt
AC
5 ms
18560 KB
sample-04.txt
AC
27 ms
104576 KB