제출 #730755

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
730755		Vu_CG_Coder	도시들 (IOI15_towns)	C++14	35 / 100	16 ms	880 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;

int f[110][110];
// int getDistance(int x , int y){
//     return f[x][y];
// }

int sub1(int N,int sub){
    int n = N;
    pair <int,int> tmp;
    vector <int> val , value;
    val.assign(n,0);
    value.assign(n,0);
    for (int i = 1 ; i < n ; i++){
        int x = getDistance(0,i);
        tmp = max(tmp,make_pair(x,i));
    }

    int u = tmp.second;
    tmp.first = 0;
    for (int i = 0 ; i < n ; i++)
    if (i != u){
        int x = getDistance(i,u);
        val[i] = x;
        tmp = max(tmp,make_pair(x,i));
    }
    int v = tmp.second;
    int R = 1e9;
    //cout << u << " " << v << "\n";

    for (int i = 0 ; i < n ; i++)
    if (i != u && i != v){
        int x = getDistance(v,i);
        value[i] = x;
        int y = val[i];
        int z = val[v];
        int a = (x + y - z)/2;
        int b = x - a;
        int c = z - b;
        int r = max(a,max(b,c));

        if (r < R){
            tmp = make_pair(b,c);
            R = r;
        }
    }

    if (sub < 3) return R;

  //  cout << tmp.first << " " << tmp.second << "\n";

    int cntu = 1 , cntv = 1 , cnt = 0;
    for (int i = 0 ; i < n ; i++) 
    if (i != u && i != v) 
    {
        int x = val[i];
        int y = val[v];
        int z = value[i];
        int a = (x + y - z)/2;

    //    cout << i << " " << a << '\n';
        
        if (a < tmp.second) cntu++;
        if (a == tmp.second) cnt++;
        if (a > tmp.second) cntv++;
    }

 //  cout << cntu << " " << cntv << " " << cnt << "\n";

    if (cntu > n/2 || cntv > n/2 || cnt > n/2) return -R;
    return R; 
}

int hubDistance(int N, int sub) {
    if (sub < 3 || sub == 4) return sub1(N,sub);
}

// int main(){
//     freopen("txt.inp","r",stdin);
//     freopen("txt.out","w",stdout);

//     int n;
//     cin >> n;
//     for (int i = 0 ; i < n ; i++)
//         for (int j = 0 ; j < n ; j++)
//             cin >> f[i][j];

//     cout << hubDistance(n,4);
//     return 0;
// }

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

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:78:1: warning: control reaches end of non-void function [-Wreturn-type]
   78 | }
      | ^

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