提出 #8223881
ソースコード 拡げる
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, B = y; i <= B; i ++)
#define ff(i, x, y) for(int i = x, B = y; i < B; i ++)
#define fd(i, x, y) for(int i = x, B = y; i >= B; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;
const int N = 1e5 + 5;
int n, m, x, y;
int a[N], b[N];
int f[N], d[N], nd[N];
int F(int x) {
return f[x] == x ? x : (f[x] = F(f[x]));
}
#define V vector<int>
#define pb push_back
#define si size()
V e[N];
int cmp(int x, int y) {
return a[x] < a[y];
}
ll sumb[N], g[N];
int main() {
scanf("%d %d", &n, &m);
fo(i, 1, n) scanf("%d %d", &a[i], &b[i]), a[i] = max(0, a[i] - b[i]);
fo(i, 1, m) {
scanf("%d %d", &x, &y);
e[x].pb(y); e[y].pb(x);
}
fo(i, 1, n) f[i] = i, sumb[i] = b[i], g[i] = a[i];
fo(i, 1, n) d[i] = i;
sort(d + 1, d + n + 1, cmp);
fo(i, 1, n) nd[d[i]] = i;
fo(i, 1, n) {
int x = d[i];
ff(j, 0, e[x].si) {
int y = e[x][j];
if(nd[y] > nd[x]) continue;
if(F(x) != F(y)) {
int u = f[x], v = f[y];
f[v] = u;
sumb[u] += sumb[v];
g[u] = min(g[u], max(g[v], a[u] - sumb[v]));
}
}
}
int x = F(d[n]);
pp("%lld\n", g[x] + sumb[x]);
}
提出情報
| 提出日時 |
|
| 問題 |
F - Donation |
| ユーザ |
cold_chair |
| 言語 |
C++14 (GCC 5.4.1) |
| 得点 |
1000 |
| コード長 |
1221 Byte |
| 結果 |
AC |
| 実行時間 |
73 ms |
| メモリ |
9468 KiB |
コンパイルエラー
./Main.cpp: In function ‘int main()’:
./Main.cpp:31: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:32:70: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
fo(i, 1, n) scanf("%d %d", &a[i], &b[i]), a[i] = max(0, a[i] - b[i]);
^
./Main.cpp:34:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &x, &y);
^
ジャッジ結果
| セット名 |
Sample |
All |
| 得点 / 配点 |
0 / 0 |
1000 / 1000 |
| 結果 |
|
|
| セット名 |
テストケース |
| Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
| All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_47.txt, subtask_1_48.txt |
| ケース名 |
結果 |
実行時間 |
メモリ |
| sample_01.txt |
AC |
2 ms |
2816 KiB |
| sample_02.txt |
AC |
2 ms |
2816 KiB |
| sample_03.txt |
AC |
2 ms |
2816 KiB |
| subtask_1_01.txt |
AC |
2 ms |
2816 KiB |
| subtask_1_02.txt |
AC |
4 ms |
2944 KiB |
| subtask_1_03.txt |
AC |
18 ms |
3840 KiB |
| subtask_1_04.txt |
AC |
2 ms |
2816 KiB |
| subtask_1_05.txt |
AC |
2 ms |
2816 KiB |
| subtask_1_06.txt |
AC |
2 ms |
2816 KiB |
| subtask_1_07.txt |
AC |
2 ms |
2816 KiB |
| subtask_1_08.txt |
AC |
2 ms |
2816 KiB |
| subtask_1_09.txt |
AC |
2 ms |
2816 KiB |
| subtask_1_10.txt |
AC |
2 ms |
2816 KiB |
| subtask_1_11.txt |
AC |
2 ms |
2816 KiB |
| subtask_1_12.txt |
AC |
2 ms |
2816 KiB |
| subtask_1_13.txt |
AC |
15 ms |
3712 KiB |
| subtask_1_14.txt |
AC |
5 ms |
3072 KiB |
| subtask_1_15.txt |
AC |
17 ms |
3840 KiB |
| subtask_1_16.txt |
AC |
55 ms |
8192 KiB |
| subtask_1_17.txt |
AC |
23 ms |
4224 KiB |
| subtask_1_18.txt |
AC |
59 ms |
8576 KiB |
| subtask_1_19.txt |
AC |
23 ms |
4352 KiB |
| subtask_1_20.txt |
AC |
60 ms |
8448 KiB |
| subtask_1_21.txt |
AC |
60 ms |
8700 KiB |
| subtask_1_22.txt |
AC |
25 ms |
5504 KiB |
| subtask_1_23.txt |
AC |
24 ms |
5376 KiB |
| subtask_1_24.txt |
AC |
17 ms |
4608 KiB |
| subtask_1_25.txt |
AC |
13 ms |
3968 KiB |
| subtask_1_26.txt |
AC |
50 ms |
7936 KiB |
| subtask_1_27.txt |
AC |
42 ms |
7040 KiB |
| subtask_1_28.txt |
AC |
4 ms |
3072 KiB |
| subtask_1_29.txt |
AC |
47 ms |
6656 KiB |
| subtask_1_30.txt |
AC |
64 ms |
8448 KiB |
| subtask_1_31.txt |
AC |
11 ms |
3456 KiB |
| subtask_1_32.txt |
AC |
71 ms |
9216 KiB |
| subtask_1_33.txt |
AC |
64 ms |
9216 KiB |
| subtask_1_34.txt |
AC |
64 ms |
9216 KiB |
| subtask_1_35.txt |
AC |
64 ms |
9216 KiB |
| subtask_1_36.txt |
AC |
69 ms |
9216 KiB |
| subtask_1_37.txt |
AC |
61 ms |
9216 KiB |
| subtask_1_38.txt |
AC |
67 ms |
9468 KiB |
| subtask_1_39.txt |
AC |
60 ms |
9468 KiB |
| subtask_1_40.txt |
AC |
61 ms |
9468 KiB |
| subtask_1_41.txt |
AC |
58 ms |
9468 KiB |
| subtask_1_42.txt |
AC |
70 ms |
9216 KiB |
| subtask_1_43.txt |
AC |
63 ms |
9216 KiB |
| subtask_1_44.txt |
AC |
63 ms |
9216 KiB |
| subtask_1_45.txt |
AC |
63 ms |
9216 KiB |
| subtask_1_46.txt |
AC |
73 ms |
9216 KiB |
| subtask_1_47.txt |
AC |
73 ms |
9216 KiB |
| subtask_1_48.txt |
AC |
73 ms |
9216 KiB |