제출 #1029734

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

towns

#include "towns.h"
#include<string.h>
#include<stdlib.h>

#include<vector>
int z;

int cache[120][120];
int l(int i, int j){return i<j?i:j;}
int h(int i, int j){return i>j?i:j;}
int ask(int i, int j) { if(cache[i][j]>=0)return cache[i][j];return cache[i][j]=cache[j][i]=(i-j ? getDistance(i, j): 0); }

int argmax(int x, int N) {
    int mx = 0, dist = -1;
    for (int y, i = 0; i < N; ++i)
        if (dist < (y = ask(x, i)))
            dist = y, mx = i, z = dist;
    return mx;
}

#include<map>
/* each branch store [arbitary node, branch length (to that node), count of leaves node in branch] */

int balance1(int d1,int d2,int dd,int R0,int N){
    memset(cache,-1,sizeof cache);
        for(int i=0;i<N;++i)for(int j=0;j<N;++j)ask(i,j);

        std::map<int,std::vector<std::array<int,3>>>M;
        int R = 1e9;
        for (int i = 0; i < N; ++i) {
            int a=ask(d1,i),b=ask(d2,i);
            int branch = (a+b-dd)/2;

            if(h(a,b)-branch<R){
                M.clear(),R=h(a,b)-branch;
                M[a-branch].push_back(std::array<int,3>{i,branch, 1});
            }
            else if(h(a,b)-branch==R){
                int found=0;
                for(auto &x:M[a-branch])
                    if(ask(x[0],i)<branch+x[1]) /* same branch */
                    {++x[2];found=1;break;}
                if(!found)
                    M[a-branch].push_back(std::array<int,3>{i,branch, 1});
            }else;
        }

        if(R>R0)return -2;
        for(auto &[_,branchinfo]:M){
            int ok=1;
            for(auto&x:branchinfo)if(x[2]>(N/2))ok=0;
            if(ok)return 1;
        }

        return -1;

}

int hubDistance(int N, int sub) {
    memset(cache,-1,sizeof cache);
    if (sub<=2){
        int d1 = argmax(0,N);
        int d2 = argmax(d1, N);
        int dd = z;

        int R = 1e9;
        for (int i = 0; i < N; ++i) {
            if(i==d1||i==d2)continue;
            int a=ask(d1,i),b=ask(d2,i);
            int branch = (a+b-dd)/2;
            R=l(R,h(a,b)-branch);
        }

        return R;
    }else if(sub==3){
        int d1 = argmax(0, N);
        int d2 = argmax(d1, N);
        int dd = z;
        for(int i=0;i<N;++i)for(int j=0;j<N;++j)ask(i,j);

        int R = 1e9;
        for (int i = 0; i < N; ++i) {
            int a=ask(d1,i),b=ask(d2,i);
            int branch = (a+b-dd)/2;
            R=l(R,h(a,b)-branch);
        }

        for(int i=0;i<N;++i)for(int j=0;j<N;++j)if(ask(i,j)==dd&&balance1(i,j,dd,R,N)==1)return R;
        return -R;
    }
}

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

towns.cpp: In function 'int balance1(int, int, int, int, int)':
towns.cpp:45:18: warning: suggest braces around empty body in an 'else' statement [-Wempty-body]
   45 |             }else;
      |                  ^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:91:1: warning: control reaches end of non-void function [-Wreturn-type]
   91 | }
      | ^

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