oj.uz

Submission #868137

# Submission time Handle Problem Language Result Execution time Memory
868137 2023-10-30T13:27:08 Z waldi Towns (IOI15_towns) C++17
61 / 100
 17 ms 1112 KB 
#include "towns.h"
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define fi first
#define se second
#define debug(a) cerr << #a << ": " << a << "\n";
using namespace std;
typedef pair<int, int> pii;

int hubDistance(int n, int sub){
	vector odpowiedz(110, vector(110, -1));
	auto zapytaj = [&](int i, int j){
		if(i > j) swap(i, j);
		if(odpowiedz[i][j]<0) odpowiedz[i][j] = getDistance(i, j);
		return odpowiedz[i][j];
	};
	
	int a = 0;
	vector<int> od0(n, 0);
	FOR(i, 1, n-1){
		od0[i] = zapytaj(0, i);
		if(od0[i] > od0[a]) a = i;
	}
	
	int b = 0;
	vector<int> oda(n, 0);
	REP(i, n) if(i != a){
		oda[i] = zapytaj(a, i);
		if(oda[i] > oda[b]) b = i;
	}
	int sred = oda[b];
	
	vector<int> odb(n, 0);
	REP(i, n) if(i != b) odb[i] = zapytaj(b, i);
	
	auto odsred = [&](int i){
		return (oda[i]+odb[i]-sred)>>1;
	};
	auto gdzie = [&](int i){
		return oda[i]-odsred(i);
	};
	auto odleglosc = [&](int i, int poz){
		return odsred(i) + abs(poz-gdzie(i));
	};
	
	set<int> secik;
	REP(i, n) secik.emplace(gdzie(i));
	
	int wyn = sred+1, poz = -1, jestgit = 0;
	for(int off : secik){
		int maks = 0;
		REP(i, n) maks = max(maks, odleglosc(i, off));
		
		int lewo = 0, prawo = 0;
		REP(i, n){
			int odla = gdzie(i);
			if(odla < off) ++lewo;
			if(odla > off) ++prawo;
		}
		int terazgit = max(lewo, prawo) <= n/2;
		
		if(maks < wyn) wyn = maks, poz = off, jestgit = terazgit;
		else if(maks == wyn && !jestgit) poz = off, jestgit = terazgit;
	}
	
	if(sub <= 2) return wyn;
	
	if(sub == 4){
		int lewo = 0, prawo = 0, ja = 0;
		REP(i, n){
			int odla = gdzie(i);
			if(odla < poz) ++lewo;
			if(odla == poz) ++ja;
			if(odla > poz) ++prawo;
		}
		bool zle = 0;
		zle |= lewo > n/2;
		zle |= prawo > n/2;
		zle |= ja > n/2;// wiem to jest jedno poddrzewo
		if(zle) wyn = -wyn;
		return wyn;
	}
	
	auto rowne = [&](int x, int y){
		return zapytaj(x, y) < odleglosc(x, poz)+odleglosc(y, poz);
	};
	int lider = 0, licznik = 1;
	FOR(i, 1, n-1){
		if(rowne(lider, i)) ++licznik;
		else --licznik;
		if(!licznik) lider = i, licznik = 1;
	}
	int ile = 0;
	REP(i, n) if(rowne(i, lider)) ++ile;
	if(ile > n/2) wyn = -wyn;
	
	return wyn;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 348 KB Output is correct
2 Correct 9 ms 784 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 12 ms 1028 KB Output is correct
5 Correct 12 ms 1044 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 344 KB Output is correct
2 Correct 9 ms 860 KB Output is correct
3 Correct 12 ms 1112 KB Output is correct
4 Correct 12 ms 860 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 12 ms 860 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 17 ms 860 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 344 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 12 ms 856 KB Output is correct
3 Correct 12 ms 860 KB Output is correct

Subtask #6
0 / 39.0

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