oj.uz

답안 #1029734

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1029734 2024-07-21T08:41:29 Z sleepntsheep 도시들 (IOI15_towns) C++17
25 / 100
 13 ms 860 KB 
#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;
    }
}

Compilation message

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

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 860 KB Output is correct
2 Correct 7 ms 860 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 13 ms 860 KB Output is correct
5 Correct 9 ms 856 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 540 KB Output is correct
2 Correct 7 ms 860 KB Output is correct
3 Correct 12 ms 860 KB Output is correct
4 Correct 11 ms 860 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -