oj.uz

Submission #432999

# Submission time Handle Problem Language Result Execution time Memory
432999 2021-06-18T17:24:43 Z wiwiho Towns (IOI15_towns) C++14
35 / 100
 21 ms 392 KB 
#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;
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 21 ms 392 KB Output is correct
2 Correct 14 ms 392 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 18 ms 380 KB Output is correct
5 Correct 18 ms 332 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 388 KB Output is correct
2 Correct 13 ms 392 KB Output is correct
3 Correct 18 ms 372 KB Output is correct
4 Correct 18 ms 384 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 388 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -