Submission #168218

#	Time	Username	Problem	Language	Result	Execution time	Memory
168218		Thuleanx	Untitled (POI11_dyn)	C++14	100 / 100	1631 ms	33900 KiB

Main

#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 (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10