oj.uz

답안 #168218

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
168218 2019-12-12T02:54:40 Z Thuleanx Dynamite (POI11_dyn) C++14
100 / 100
 1631 ms 33900 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 3e5+7, oo = 1e9;

int n, m;
vector<int> adj[N];
int dist;
int tob[N], toig[N], cnt[N];
bool isb[N];

// ignite at the very last minute
void run(int v, int p) {
	tob[v] = isb[v]?0:-oo;	
	toig[v] = -oo;
	cnt[v] = 0;
	for (int w : adj[v]) if (w != p) {
		run(w, v);
		tob[v] = max(tob[v], tob[w]+1);
		toig[v] = max(toig[v], toig[w]-1);
		cnt[v] += cnt[w];
	}

	// ignition can cover for bomb
	if (toig[v] >= tob[v]) 
		tob[v] = -oo;
	if (tob[v] >= dist) {
		cnt[v]++;
		tob[v] = -oo;
		toig[v] = dist;
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin>>n>>m;
	for (int i = 0; i < n; i++)
		cin>>isb[i];
	for (int i = 0; i < n-1; i++) {
		int a, b; cin>>a>>b;
		adj[--a].push_back(--b);
		adj[b].push_back(a);
	}

	int lo = 0, hi = N;
	while (lo <= hi) {
		dist = lo+hi>>1;		
		run(0, -1);
		if (tob[0] >= 0)
			cnt[0]++;
		if (cnt[0] > m) 
			lo = dist+1;
		else hi = dist-1;
	}
	cout << lo << endl;

	return 0;
}

Compilation message

dyn.cpp: In function 'int main()':
dyn.cpp:50:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   dist = lo+hi>>1;  
          ~~^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7420 KB Output is correct
2 Correct 21 ms 7416 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 7928 KB Output is correct
2 Correct 45 ms 8784 KB Output is correct
3 Correct 48 ms 9064 KB Output is correct
4 Correct 61 ms 10484 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 10488 KB Output is correct
2 Correct 100 ms 11628 KB Output is correct
3 Correct 154 ms 12128 KB Output is correct
4 Correct 151 ms 14444 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 13436 KB Output is correct
2 Correct 159 ms 13456 KB Output is correct
3 Correct 229 ms 13176 KB Output is correct
4 Correct 554 ms 17528 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 581 ms 19536 KB Output is correct
2 Correct 714 ms 21752 KB Output is correct
3 Correct 1092 ms 28340 KB Output is correct
4 Correct 1185 ms 28152 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1474 ms 27312 KB Output is correct
2 Correct 1093 ms 26232 KB Output is correct
3 Correct 1530 ms 29560 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1328 ms 32304 KB Output is correct
2 Correct 1008 ms 26116 KB Output is correct
3 Correct 1631 ms 33900 KB Output is correct
4 Correct 394 ms 26388 KB Output is correct