Submission #433019

#	Time	Username	Problem	Language	Result	Execution time	Memory
433019		wiwiho	Towns (IOI15_towns)	C++14	26 / 100	21 ms	900 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(u == v) return 0;
    //cerr << "query " << u << " " << v << " " << qry[u][v] << "\n";
    if(qry[u][v] == -1){
        int tmp = getDistance(u, v);
        qry[u][v] = qry[v][u] = tmp;
    }
    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), oao(n);
    for(int i = 0; i < n; i++){
        int sum = query(v1, i) + query(v2, i);
        oao[i] = (sum - dia) / 2;
        ld[i] = query(v1, i) - oao[i];
        rd[i] = query(v2, i) - oao[i];
        ans = min(ans, max(ld[i], rd[i]));
    }
    //cerr << ans << "\n";
    
    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;
    vector<int> lh, rh;
    //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.eb(i);
        else if(rd[i] == rmn) rh.eb(i);
    }
    int lhsz = 0, rhsz = 0;
    for(int i : lh){
        int sz = 0;
        for(int j : lh){
            if(query(i, j) < oao[i] + oao[j]) sz++;
        }
        lhsz = max(sz, lhsz);
    }
    for(int i : rh){
        int sz = 0;
        for(int j : rh){
            if(query(i, j) < oao[i] + oao[j]) sz++;
        }
        rhsz = max(sz, rhsz);
    }

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

	return ans;
}

Compilation message (stderr)

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

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