提出 #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
結果
AC × 3
AC × 54
セット名 テストケース
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