Submission #483181

#	Time	Username	Problem	Language	Result	Execution time	Memory
483181		thomas_li	Towns (IOI15_towns)	C++17	25 / 100	16 ms	1152 KiB

towns

// full
#include <bits/stdc++.h>
using namespace std;
int getDistance(int i, int j);

int hubDistance(int N, int sub){
    int n = N,a = 0, b = 0, r = 1e9; vector<vector<int>> dist(n,vector<int>(n,-1));
    auto get = [&](int x, int y){
        if(x == y) return 0;
        if(x > y) swap(x,y);
        if(dist[x][y] != -1) return dist[x][y];
        return dist[x][y] = getDistance(x,y);
    };
    for(int i = 0; i < n; i++){
        if(get(0,i) > get(0,a)){
            a = i;
        } 
    }  
    for(int i = 0; i < n; i++){
        if(get(a,i) > get(a,b)){
            b = i;
        }
    }
    map<int,vector<int>> mp;
    for(int i = 0; i < n; i++){
        int da = (get(a,0) + get(a,i) - get(0,i)) / 2;
        r = min(r,max(da,get(a,b)-da));
        mp[da].emplace_back(i);
    } 
    set<int> lft,rit;
    for(int i = 0; i < n; i++) rit.insert(i);
    int pre = 0, suf = n;
    for(auto&[da,vec]:mp){
        suf -= vec.size();
        for(int u : vec) rit.erase(u);
        if(suf <= n/2 && pre <= n/2 && r == max(da,get(a,b)-da)){
            set<int> s(vec.begin(),vec.end());
            auto same = [&](int x, int y){
                if(s.find(x) == s.end() && s.find(y) == s.end()){
                    return bool(lft.find(x) == lft.end()) == bool(lft.find(y) == lft.end()); 
                } else if(s.find(x) == s.end() || s.find(y) == s.end()) return false;
                return get(a,x) + get(a,y) - get(x,y) > 2*r;
            };
            vector<int> ls,bk;
            for(int u : vec){
                if(ls.empty() || !same(ls.back(),u)){
                    ls.emplace_back(u);
                    if(bk.size()){
                        ls.emplace_back(bk.back());
                        bk.pop_back();
                    }
                } else{
                    bk.emplace_back(u);
                }
            }
            int t = ls.back(),sz = 0; bool maj = 0;
            while(ls.size()){
                if(same(ls.back(),t)){
                    if(ls.size() == 1){
                        maj = 1;
                        sz++;
                        break;
                    }
                    sz++;
                    ls.pop_back(); ls.pop_back();
                } else{
                    ls.pop_back();
                    if(bk.empty()){
                        maj = 0;
                        break;
                    }
                    sz++;
                    bk.pop_back();
                }
            }
            sz += bk.size();
            if(bk.size()) maj = 1;
            return (sz <= n/2 ? 1 : -1) * r;
            
        } 
        pre += vec.size();
        for(int u : vec) lft.insert(u);
    }
    return r;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:34:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   34 |         suf -= vec.size();
      |                         ^
towns.cpp:76:27: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   76 |             sz += bk.size();
      |                           ^
towns.cpp:56:44: warning: variable 'maj' set but not used [-Wunused-but-set-variable]
   56 |             int t = ls.back(),sz = 0; bool maj = 0;
      |                                            ^~~
towns.cpp:81:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   81 |         pre += vec.size();
      |                         ^
towns.cpp:6:28: warning: unused parameter 'sub' [-Wunused-parameter]
    6 | int hubDistance(int N, int sub){
      |                        ~~~~^~~

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