oj.uz

Submission #341318

# Submission time Handle Problem Language Result Execution time Memory
341318 2020-12-29T13:13:55 Z mario05092929 Dynamite (POI11_dyn) C++11
30 / 100
 1695 ms 33768 KB 
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast") 
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 2e18;
const long long mod = 1e9+7;
const long long hashmod = 100003;
const int MAXN = 100000;
const int MAXM = 1000000;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
int n,k,cnt,len;
int isd[300005];
int nam[300005],dist[300005];
vec v[300005];

void dfs(int x,int pr) {
	dist[x] = -INF*(1-isd[x]);
	nam[x] = -INF;
	for(int i : v[x]) {
		if(i == pr) continue;
		dfs(i,x);
		dist[x] = max(dist[x],dist[i]+1);
		nam[x] = max(nam[x],nam[i]-1);
	}
	if(nam[x] >= dist[x]) dist[x] = -INF;
	if(dist[x] >= len) {
		cnt++;
		dist[x] = -INF;
		nam[x] = len;
	}
}

bool isok(int mid) {
	len = mid, cnt = 0;
	dfs(1,-1);
	return (cnt <= k);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> k;
	for(int i = 1;i <= n;i++) cin >> isd[i];
	for(int i = 1;i < n;i++) {
		int x,y; cin >> x >> y;
		v[x].pb(y), v[y].pb(x);
	}
	int l = 0, r = n;
	while(l < r) {
		int mid = (l + r) >> 1;
		if(isok(mid)) r = mid;
		else l = mid+1;
	}
	cout << l;
}

Compilation message

dyn.cpp:6: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    6 | #pragma gcc optimize("O3")
      | 
dyn.cpp:7: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    7 | #pragma gcc optimize("Ofast")
      | 
dyn.cpp:8: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    8 | #pragma gcc optimize("unroll-loops")
      |

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7404 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Correct 5 ms 7404 KB Output is correct
4 Incorrect 5 ms 7404 KB Output isn't correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Output is correct
2 Correct 6 ms 7404 KB Output is correct
3 Correct 5 ms 7404 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 7404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7404 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7916 KB Output is correct
2 Correct 36 ms 8684 KB Output is correct
3 Correct 37 ms 9068 KB Output is correct
4 Correct 51 ms 11008 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 10604 KB Output is correct
2 Correct 162 ms 11628 KB Output is correct
3 Correct 202 ms 12012 KB Output is correct
4 Incorrect 227 ms 14828 KB Output isn't correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 13344 KB Output is correct
2 Correct 305 ms 13548 KB Output is correct
3 Correct 394 ms 13292 KB Output is correct
4 Incorrect 424 ms 18540 KB Output isn't correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 813 ms 19308 KB Output is correct
2 Correct 1004 ms 21484 KB Output is correct
3 Incorrect 1338 ms 29548 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1695 ms 27744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1589 ms 33768 KB Output isn't correct
2 Halted 0 ms 0 KB -