oj.uz

Submission #837366

# Submission time Handle Problem Language Result Execution time Memory
837366 2023-08-25T09:57:49 Z pomuchle Towns (IOI15_towns) C++17
0 / 100
 13 ms 980 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -