Submission #837366

#	Time	Username	Problem	Language	Result	Execution time	Memory
837366		pomuchle	Towns (IOI15_towns)	C++17	0 / 100	13 ms	980 KiB

towns

#include "towns.h"
#include <map>
#include <ios>
#include <vector>
#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) {
    auto que=[&](int p, int k){
        return getDistance(p, k);
    };
    int n=N+(sub==-1);
    vi odlp(n),odlk(n),kodl(n);
    vi 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]=i==p ? 0 : que(i, p);
                if (odlp[i]>maxodl)
                    maxodl=odlp[i],k=i;
            }
        }
        {
            int maxodl=-1;
            REP(i, n){
                odlk[i]=i==k ? 0 : 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.clear();
            if (l<=R)
                srv.emplace_back(i);
        }
    }
    bool bal=0;
    // max 2 w srv
    for (int i : srv){
        int ilel=0,ilep=0;
        vi synv;
        for (const auto &[odl, v] : kub){
            if (odl<kodl[i])
                ilel+=sz(v);
            else if (odl>kodl[i])
                ilep+=sz(v);
            else
                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 (odlp[a]+odlp[b]-kodl[a]*2)!=que(a, b);
        };
        V <vi> spoj;
        int l,p;
        for (int j : synv){
            if (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;
            }
        }
        // spojna p to nasz potencjalny kandydat
        int ilew=0,ilepoza=0;
        REP(j, sz(spoj)){
            if (j==p)
                ilew+=sz(spoj[j]);
            else if (abs(j-p)==1)
                ilepoza+=sz(spoj[j]);
            else if (!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){
                bal=1;
                break;
            }
            if (sz(synv)-ilepoza<=n/2)
                break;
        }
        if (bal)
            break;
    }
	return bal ? R : -R;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:84:17: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |                 if (p!=sz(spoj)-1)
      |                 ^~
towns.cpp:87:21: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |                     ++l;
      |                     ^~~

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