제출 #837388

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

towns

#include "towns.h"
#include <map>
#include <cstdlib>
#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) {
    int cap;
    switch (sub){
        case 1: cap=N*(N-1)/2; break;
        case 2: cap=7*N/2+7*N%2; break;
        case 3: cap=N*(N-1)/2; break;
        case 4: cap=7*N/2+7*N%2; break;
        case 5: cap=N*5; break;
        case 6: cap=7*N/2+7*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);
    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]=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.clear();
            if (l<=R)
                srv.emplace_back(i);
        }
    }
    bool bal=sub<3;
    // max 2 w srv
    if (sub>=3){
        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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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