제출 #432999

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

towns

#include "towns.h"

#include <bits/stdc++.h>
 
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}
#define mp make_pair
#define F first
#define S second
#define eb emplace_back
#define iter(a) a.begin(), a.end()
 
using namespace std;
 
typedef long long ll;
 
using pii = pair<int, int>;
 
const ll MOD = 1000000007;
const ll MAX = 1000000000;

vector<vector<int>> qry;

int n;
int query(int u, int v){
    if(qry[u][v] == -1) qry[u][v] = getDistance(u, v);
    return qry[u][v];
}

vector<int> dis(int v){
    vector<int> ans(n);
    for(int i = 0; i < n; i++) ans[i] = query(v, i);
    return ans;
}

int hubDistance(int N, int sub){
    qry.clear();
    n = N;
    qry.resize(n, vector<int>(n, -1));

    vector<int> d0 = dis(0);
    int v1 = max_element(iter(d0)) - d0.begin();
    vector<int> d1 = dis(v1);
    int v2 = max_element(iter(d1)) - d1.begin();
    vector<int> d2 = dis(v2);
    //cerr << v1 << " " << v2 << "\n";

    int dia = query(v1, v2);

    int ans = MAX;
    vector<int> ld(n), rd(n);
    for(int i = 0; i < n; i++){
        int sum = query(v1, i) + query(v2, i);
        int oao = (sum - dia) / 2;
        ld[i] = query(v1, i) - oao;
        rd[i] = query(v2, i) - oao;
        ans = min(ans, max(ld[i], rd[i]));
    }
    
    int lmn = MAX, rmn = MAX;
    for(int i = 0; i < n; i++){
        if(ld[i] == ans || rd[i] == ans){
            lmn = min(lmn, ld[i]);
            rmn = min(rmn, rd[i]);
        }
    }

    int lb = 0, rb = 0, lh = 0, rh = 0;
    //cerr << lmn << " " << rmn << "\n";
    for(int i = 0; i < n; i++){
        //cerr << i << " " << ld[i] << " " << rd[i] << "\n";
        if(ld[i] < lmn) lb++;
        else if(rd[i] < rmn) rb++;
        else if(ld[i] == lmn) lh++;
        else if(rd[i] == rmn) rh++;
    }
    //cerr << lb << " " << rb << " " << lh << " " << rh << "\n";

    if(max({lb, rb, lh, rh}) > n / 2) ans = -ans;

	return ans;
}

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

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:44:36: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   44 |     int v1 = max_element(iter(d0)) - d0.begin();
      |              ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp:46:36: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   46 |     int v2 = max_element(iter(d1)) - d1.begin();
      |              ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp:38:28: warning: unused parameter 'sub' [-Wunused-parameter]
   38 | int hubDistance(int N, int sub){
      |                        ~~~~^~~

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