Submission #837638

#	Time	Username	Problem	Language	Result	Execution time	Memory
837638		pomuchle	Towns (IOI15_towns)	C++17	48 / 100	13 ms	852 KiB

towns

#include "towns.h"
#include <map>
#include <cassert>
#include <cstdlib>
#include <vector>
#include <set>
#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, p, n) for(int i=(p); i<=(n); ++i)
#define V std::vector
#define sz(A) (int(A.size()))
typedef long long ll;
typedef V <int> vi;
typedef V <ll> vll;


int hubDistance(int N, int sub) {
    int cap;
    switch (sub){
        case 1: cap=N*(N-1)/2; break;
        case 2: cap=7*N/2+N%2; break;
        case 3: cap=N*(N-1)/2; break;
        case 4: cap=7*N/2+N%2; break;
        case 5: cap=N*5; break;
        case 6: cap=7*N/2+N%2; break;
    }
    auto que=[&](int p, int k){
        cap-=p!=k;
        if (cap<0)
            exit(69);
        return p==k ? 0 : getDistance(p, k);
    };
    int n=N;
    vi odlp(n),odlk(n),kodl(n);
    std::set <int> srv;
    std::map <int, vi> kub; // kub[odl do p]=zbior poddrzew zioma
    int R=1e9;
    {
        int p=0,k=-1,k22=-1;
        {
            int maxodl=-1;
            REP(i, n){
                odlp[i]=que(i, p);
                if (odlp[i]>maxodl)
                    maxodl=odlp[i],k=i;
            }
        }
        {
            int maxodl=-1;
            REP(i, n){
                odlk[i]=que(i, k);
                if (odlk[i]>maxodl)
                    maxodl=odlk[i],k22=i;
            }
        }
        REP(i, n){
            kodl[i]=(odlk[i]-odlp[i]+odlp[k])/2;
            int k22odl=odlk[k22]-kodl[i];
            kub[kodl[i]].emplace_back(i);
            int l=std::max(kodl[i], k22odl);
            if (l<R)
                R=l,srv={};
            if (l<=R)
                srv.insert(kodl[i]);
        }
    }
    bool bal=sub<3;
    // max 2 w srv
    if (sub>=3){
        assert(srv.size()<3);
        for (int srkodl : srv){
            int ilel=0,ilep=0;
            vi synv;
            for (const auto &[odl, v] : kub){
                if (odl<srkodl)
                    ilel+=sz(v);
                else if (odl>srkodl)
                    ilep+=sz(v);
                else{
                    assert(synv.empty());
                    synv=v;
                }
            }
            if (std::max(ilel, ilep)>n/2)
                continue;
            if (sz(synv)<=n/2){
                bal=1;
                break;
            }
            auto spr=[&](int a, int b){ // true jezeli sa w tym samym
                return (odlk[a]+odlk[b]-srkodl*2)!=que(a, b);
            };
            V <vi> spoj;
            int l,p;
            for (int j : synv){
                bool idk=0;
                for (auto &v : spoj)
                    if (spr(v[0], j)){
                        idk=1;
                        v.emplace_back(j);
                        break;
                    }
                if (idk)
                    continue;
                if (!idk||spoj.empty()){
                    spoj.push_back({j});
                    l=1,p=0;
                    continue;
                }
                if (spr(spoj.back()[0], j)){
                    spoj.back().emplace_back(j);
                    if (p!=sz(spoj)-1)
                        --l;
                    else
                        ++l;
                    if (!l)
                        l=1,p=sz(spoj)-1;
                }
                else{
                    spoj.push_back({j});
                    --l;
                    if (!l)
                        l=1,p=sz(spoj)-1;
                }
            }
            l=-1;
            REP(j, sz(spoj))
                if (sz(spoj[j])>l)
                    l=sz(spoj[j]),p=j;
            int ile=0;
            for (int i : synv)
                if (spr(spoj[p][0], i))
                    ++ile;
            // spojna p to nasz potencjalny kandydat
            int ilew=0,ilepoza=0;
            REP(j, sz(spoj)){
                if (abs(j-p)==1||!spr(spoj[j][0], spoj[p][0]))
                    ilepoza+=sz(spoj[j]);
                else{
                    ilew+=sz(spoj[j]);
                    if (++j<sz(spoj))
                        ilepoza+=sz(spoj[j]);
                }
                if (ilew>n/2||sz(synv)-ilepoza<=n/2)
                    break;
            }
            assert((sz(synv)-ilepoza<=n/2)==(ile<=n/2));
            if (sz(synv)-ilepoza<=n/2)
                bal=1;
        }
    }
	return bal ? R : -R;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:136:26: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
  136 |                 if (abs(j-p)==1||!spr(spoj[j][0], spoj[p][0]))
      |                         ~^~
towns.cpp:17:9: warning: 'cap' may be used uninitialized in this function [-Wmaybe-uninitialized]
   17 |     int cap;
      |         ^~~

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