oj.uz

Submission #434068

# Submission time Handle Problem Language Result Execution time Memory
434068 2021-06-20T14:39:35 Z qwerasdfzxcl Towns (IOI15_towns) C++14
100 / 100
 27 ms 892 KB 
#include "towns.h"
#include <bits/stdc++.h>

using namespace std;
int dist[111][111], n, a = 0, b;

void getdistD(int hub, vector<int>& distD){
    for (int i=1;i<n;i++) if (i!=b){
        int y = dist[a][b]-dist[b][i]+(dist[a][i]+dist[b][i]-dist[a][b])/2;
        int z = dist[a][b] - y;
        if (y<=hub) distD[i] = dist[a][i]-y+(hub-y);
        else distD[i] = dist[b][i]-z+(dist[a][b]-hub-z);
    }
    distD[0] = hub;
    distD[b] = dist[a][b] - hub;
}

int hubDistance(int N, int sub) {
	n = N;
	for (int i=0;i<n;i++) fill(dist[i], dist[i]+n, 0);
    for (int i=1;i<n;i++) dist[0][i] = getDistance(0, i);
    b = max_element(dist[0], dist[0]+n) - dist[0];
    for (int i=1;i<n;i++) if (i!=b) dist[b][i] = getDistance(b, i);
    set<int> st;
    for (int i=1;i<n;i++) if (i!=b){
        st.insert(dist[a][b]-dist[b][i]+(dist[a][i]+dist[b][i]-dist[a][b])/2);
    }

    dist[b][a] = dist[a][b];
    int ret = dist[a][b];
    vector<int> candidate;
    for (auto &x:st){
        int tmp = max(x, dist[a][b]-x);
        for (int i=1;i<n;i++){
            int y = dist[a][b]-dist[b][i]+(dist[a][i]+dist[b][i]-dist[a][b])/2;
            int z = dist[a][b] - y;
            if (y<=x) tmp = max(tmp, dist[a][i]-y+(x-y));
            else tmp = max(tmp, dist[b][i]-z+(dist[a][b]-x-z));
        }
        if (ret>tmp){
            candidate.clear(); ret = tmp;
        }
        if (ret==tmp) candidate.push_back(x);
    }

    assert((int)candidate.size()<=2);
    int hub;
    vector<int> distD(N);
    if ((int)candidate.size()==2){
        if (candidate[0]>candidate[1]) swap(candidate[0], candidate[1]);
        int cnt1 = n, cnt2 = n;
        getdistD(candidate[0], distD);
        for (int i=0;i<N;i++) if (dist[b][i]<distD[b]+distD[i]) cnt1--;
        getdistD(candidate[1], distD);
        for (int i=0;i<N;i++) if (dist[a][i]<distD[a]+distD[i]) cnt2--;
        if (cnt1==cnt2) return ret;
        else if (cnt1>cnt2) hub = candidate[0];
        else hub = candidate[1];
    }
    else hub = candidate[0];

    getdistD(hub, distD);
    //for (int i=0;i<n;i++) printf("%d ", distD[i]);
    //printf("\n");

    int cnta = 0, cntb = 0;
    set<int> C;
    for (int i=0;i<n;i++) C.insert(i);
    for (int i=0;i<n;i++){
        if (dist[a][i]<distD[a]+distD[i]){
            cnta++; C.erase(C.find(i));
        }
        if (dist[b][i]<distD[b]+distD[i]){
            cntb++; C.erase(C.find(i));
        }
    }
    if (cnta>n/2 || cntb>n/2) return -ret;

    ///Boyer-Moore
    stack<int> st1;
    vector<int> C1;
    for (auto &x:C) C1.push_back(x);
    int mx = C1.size();

    vector<int> zero(1);
    vector<bool> col(mx);
    for (int i=0;i<mx;i++){
        if (st1.empty()){
            st1.push(C1[i]); col[i] = 1; continue;
        }
        int x = st1.top();
        if (getDistance(x, C1[i])<distD[x]+distD[C1[i]]){
            st1.push(C1[i]); col[i] = 1;
        }
        else{
            st1.pop();
            if (st1.empty()) zero.push_back(i+1);
        }
    }
    if (st1.empty()) return ret;
    int cnt3 = 0;
    for (int i=0;i<(int)zero.size()-1;i++){
        int tmp1 = 0;
        for (int j=zero[i];j<zero[i+1];j++){
            if (col[j]){
                tmp1++; continue;
            }
            if (getDistance(st1.top(), C1[j])<distD[st1.top()]+distD[C1[j]]) cnt3++;
        }
        if (getDistance(st1.top(), C1[zero[i]])<distD[st1.top()]+distD[C1[zero[i]]]) cnt3 += tmp1;
    }
    for (int j=zero.back();j<mx;j++) if (col[j]) cnt3++;
    if (cnt3>n/2) return -ret;
    return ret;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:22:41: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   22 |     b = max_element(dist[0], dist[0]+n) - dist[0];
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
towns.cpp:83:21: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   83 |     int mx = C1.size();
      |              ~~~~~~~^~
towns.cpp:18:28: warning: unused parameter 'sub' [-Wunused-parameter]
   18 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 332 KB Output is correct
2 Correct 14 ms 396 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 19 ms 332 KB Output is correct
5 Correct 19 ms 332 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 392 KB Output is correct
2 Correct 14 ms 396 KB Output is correct
3 Correct 19 ms 332 KB Output is correct
4 Correct 19 ms 332 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 396 KB Output is correct
2 Correct 20 ms 888 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 26 ms 844 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 332 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 396 KB Output is correct
2 Correct 19 ms 844 KB Output is correct
3 Correct 27 ms 892 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 332 KB Output is correct
2 Correct 20 ms 888 KB Output is correct
3 Correct 19 ms 844 KB Output is correct