제출 #383861

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
383861		LucaDantas	도시들 (IOI15_towns)	C++17	25 / 100	27 ms	492 KiB

towns

    #include "towns.h"
    #include <cstring>
    #include <cstdio>
    #include <algorithm>
    #include <cassert>
    #include <vector>
    #include <map>
     
    constexpr int maxn = 120;
     
    int dp[maxn][maxn], c[maxn], n;
     
    std::map<int, std::vector<int>> filhos;
     
    int get(int i, int j) {
    	if(i > j) std::swap(i, j);
    	if(dp[i][j] != -1) return dp[i][j];
    	return dp[i][j] != -1 ? dp[i][j] : dp[i][j] = getDistance(i, j);
    }
     
    int max(int a, int b) { return a > b ? a : b; }
    int min(int a, int b) { return a < b ? a : b; }
     
    int hubDistance(int N, int sub) {
    	n = N;
    	memset(dp, -1, sizeof dp);
    	memset(c, -1, sizeof c);
    	filhos.clear();
    	int a = 0, b = 0, dist = 0;
    	for(int i = 0; i < 2; i++) {
    		for(int j = 0; j < N; j++) {
    			if(a != j) {
    				int v = get(a, j);
    				if(v > dist) b = j, dist = v;
    			}
    		}
    		if(!i) a = b, dist = 0, b = 0;
    	}
    	int R = 0x3f3f3f3f;
    	for(int i = 0; i < N; i++) {
    		if(i == a || i == b) continue;
    		int d1 = get(a, i), d2 = get(b, i);
    		c[i] = (d1 + d2 - dist) >> 1;
    		R = min(R, max(d1, d2) - c[i]);
    		filhos[d1].push_back(i);
    	}
    	if(sub <= 2) return R;
    	if(sub != 4) assert(0);
    	int sz = 1;
    	bool ok = 0;
    	for(auto it : filhos) {
    		if(it.first != R && it.first != dist - R) {
    			sz += (int)(it.second).size();
    			continue;
    		}
    		if(sz > (n >> 1) || n - sz - (int)(it.second).size() > (n >> 1)) break;
    		std::vector<int> v = (it.second);
    		// n sei por enquanto mas sei q se chegou até aq a sub4 tá safe
    		ok = 1;
    	}
    	return R * (ok?1:-1);
    }

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39