oj.uz

Submission #349906

# Submission time Handle Problem Language Result Execution time Memory
349906 2021-01-18T16:30:21 Z pit4h Towns (IOI15_towns) C++14
100 / 100
 25 ms 1004 KB 
#include<bits/stdc++.h>
#include "towns.h"
using namespace std;
const int MAXN = 111;
int dist[MAXN][MAXN];
int n, subtask;
int l=-1, r=-1;
int queries;
int GetDistance(int i, int j) {
	queries++;
	return getDistance(i, j);
}
int dist_to_lca(int i, int j, int k) {
	return dist[i][k] - (dist[i][k] + dist[j][k] - dist[i][j])/2;
}
int dist_to_hub(int i, int j, int d) {
	return dist[i][j] - d;	
}
bool is_balanced(vector<int> vec, int rt, int d) {
	if((int)vec.size() <= n/2) return true;
	vector<int> cand;
	vector<bool> popped(n), is_leader(n);
	for(int i: vec) {
		if(cand.empty()) {
			cand.push_back(i);
		}
		else {
			if(GetDistance(cand.back(), i) < dist_to_hub(cand.back(), rt, d) + dist_to_hub(i, rt, d)) {
				popped[i] = 0;
				cand.push_back(i);	
			}
			else {
				popped[i] = 1;
				cand.pop_back();
			}
		}
	}
	if(cand.empty()) {
		return true;
	}
	int leader = cand.back();
	is_leader[leader] = 1;
	cand.clear();
	int cnt = 0;
	for(int i: vec) {
		if(cand.empty()) {
			cand.push_back(i);
			if(GetDistance(i, leader) < dist_to_hub(i, rt, d) + dist_to_hub(leader, rt, d)) {
				cnt++;
				is_leader[i] = 1;
			}
		}
		else {
			if(!popped[i]) {
				if(is_leader[cand.back()]) {
					cnt++;
					is_leader[i] = 1;
				}
				cand.push_back(i);
			}
			else {
				if(GetDistance(i, leader) < dist_to_hub(i, rt, d) + dist_to_hub(leader, rt, d)) {
					cnt++;
					is_leader[i] = 1;
				}		
				cand.pop_back();
			}
		}
	}
	if(cnt <= n/2) return true;
	else return false;
}
int hubDistance(int N, int sub) {
	subtask = sub;
	n = N;
	l = -1;
	r = -1;
	queries = 0;
	for(int i=1; i<n; ++i) {
		dist[0][i] = GetDistance(0, i);
		dist[i][0] = dist[0][i];
		if(l==-1 || dist[0][i] > dist[0][l]) {
			l = i;
		}
	}
	for(int i=0; i<n; ++i) {
		if(i==l) continue;
		dist[l][i] = GetDistance(l, i);
		dist[i][l] = dist[l][i];
		if(r==-1 || dist[l][i] > dist[l][r]) {
			r = i;
		}
	}
	int R = 1e9+1;
	vector<vector<int>> half(2, vector<int>());
	vector<bool> is_hub(2);
	for(int i=0; i<n; ++i) {
		int dl = dist_to_lca(l, 0, i);
		int rc = max(dl, dist[l][r] - dl);
		if(rc < R) {
			is_hub[0] = is_hub[1] = 0;
		}
		if(i!=0) R = min(R, rc);
		if(rc==R) {
			is_hub[dl >= (dist[l][r]-1)/2+1] = 1;
		}
		if(dl < (dist[l][r]-1)/2+1) {
			half[0].push_back(i);
		}
		else {
			half[1].push_back(i);
		}
	}
	if((is_hub[0] && is_balanced(half[0], 0, dist[0][l] - (dist[l][r] - R)) && (int)half[1].size() <= n/2) || (is_hub[1] && is_balanced(half[1], l, R) && (int)half[0].size() <= n/2)) {
		return R;
	}
	else {
		return -R;
	}
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 364 KB Output is correct
2 Correct 14 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 19 ms 492 KB Output is correct
5 Correct 19 ms 364 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 364 KB Output is correct
2 Correct 14 ms 364 KB Output is correct
3 Correct 19 ms 364 KB Output is correct
4 Correct 21 ms 492 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 364 KB Output is correct
2 Correct 20 ms 1004 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 20 ms 980 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 364 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 364 KB Output is correct
2 Correct 20 ms 1004 KB Output is correct
3 Correct 22 ms 1004 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 364 KB Output is correct
2 Correct 25 ms 1004 KB Output is correct
3 Correct 20 ms 1004 KB Output is correct