Submission #600263

#	Time	Username	Problem	Language	Result	Execution time	Memory
600263		leaked	Towns (IOI15_towns)	C++17	25 / 100	19 ms	440 KiB

towns

#include <bits/stdc++.h>
#include "towns.h"

#define f first
#define s second
#define m_p make_pair
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)(x).size()
#define vec vector

using namespace std;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}

typedef long long ll;
typedef pair<int,int> pii;

map<pii,int> mp;
int dist(int i,int j){
    if(i==j || mp.count({i,j}))
        return mp[{i,j}];
    mp[{i,j}]=mp[{j,i}]=getDistance(i,j);
    return mp[{i,j}];
}
int n;
int getcnt(int sub){
    if(sub==5)
        return 2;
    if(sub==1 || sub==3)
        return n;
    return 0;
}
int hubDistance(int n, int sub){
    int v,u;
    ::n=n;
    mp.clear();
    srand(n*sub);
    int ft=rand()%n;
    vec<int> r(n);
    {
//        vec<int> r(n);
        for(int i=0;i<n;i++) r[i]=dist(ft,i);
        v=max_element(all(r))-r.begin();
    }

    vec<int> r1(n),r2(n);
    for(int i=0;i<n;i++) r1[i]=dist(v,i);

    u=max_element(all(r1))-r1.begin();



    vec<pii> cand;

    vec<int> d1(n),d2(n);
    vec<int> rasts;
    vec<int> pref,suf;

    vec<int> c1,c2;

    map<int,int> mp;
    map<int,int> cntk;


    for(int i=0;i<n;i++){
//        r2[i]=dist(u,i);

        int s=(r1[i]+r1[ft]-r[i]);

        assert((s%2)==0);
        s/=2;
        d2[i]=s;

        d1[i]=r1[i]-s;

        umax(mp[d2[i]],d1[i]);
        ++cntk[d2[i]];

    }
    for(auto &z : mp)
        rasts.pb(z.f),pref.pb(z.s);

    for(auto &z : cntk) c1.pb(z.s);


    suf=pref;c2=c1;

    for(int i=1;i<sz(rasts);i++)
        umax(pref[i],pref[i-1]+rasts[i]-rasts[i-1]),c1[i]+=c1[i-1];
    for(int i=sz(rasts)-2;i>=0;i--)
        umax(suf[i],suf[i+1]+rasts[i+1]-rasts[i]),c2[i]+=c2[i+1];


    int mn=1e9;
    for(int i=0;i<sz(rasts);i++){
        umin(mn,max(pref[i],suf[i]));
    }


    int cen = -1;
    int ok=0;
    for(int i=0;i<sz(rasts);i++){
        if(max(pref[i],suf[i])!=mn) continue;
        int f=(i?c1[i-1]:0),s=(i+1==sz(rasts)?0:c2[i+1]);
//        int t=c1[i]-f;
        if(f<=(n/2) && s<=(n/2))
            cen=i;
    }
    if(cen == -1) return -mn;

    auto check=[&](int x,int y){
        if(x == y) return 1;
        int my=d1[x]+abs(d2[x]-rasts[cen]);
        int his=d1[y]+abs(d2[y]-rasts[cen]);
        if((my+his)!=dist(x,y)) return 1;
        return 0;
    };

    vec<int> cnt(n);
    int mb=0;
    int h=0;
    map<int,int> ban;
    for(int i=0;i<n;i++){
        if(d2[i]==d2[cen]){
            if(!h) mb=i,ban.clear();
            if(check(mb,i)) ++h,++cnt[mb];
            else --h,ban[i]=1,cnt[i]=1;
        }
    }
    int cntr=0;
    for(int i=0;i<n;i++){
        if(d2[i]==d2[cen] && !ban[i] && cnt[i]){
            cntr+=(cnt[i]*check(i,mb));
        }
    }

//    int ok=0;

////    cout<<"OK "<<ok<<endl;
    if(cntr>(n/2)) mn*=-1;
//    cout<<"W "<<mn<<endl;
    return mn;
}
/*
3 1
11
0 17 18 20 17 12 20 16 23 20 11
17 0 23 25 22 17 25 21 28 25 16
18 23 0 12 21 16 24 20 27 24 17
20 25 12 0 23 18 26 22 29 26 19
17 22 21 23 0 9 21 17 26 23 16
12 17 16 18 9 0 16 12 21 18 11
20 25 24 26 21 16 0 10 29 26 19
16 21 20 22 17 12 10 0 25 22 15
23 28 27 29 26 21 29 25 0 21 22
20 25 24 26 23 18 26 22 21 0 19
11 16 17 19 16 11 19 15 22 19 0

*/

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:36:21: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   36 | int hubDistance(int n, int sub){
      |                 ~~~~^
towns.cpp:28:5: note: shadowed declaration is here
   28 | int n;
      |     ^
towns.cpp:46:30: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   46 |         v=max_element(all(r))-r.begin();
      |           ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
towns.cpp:52:27: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   52 |     u=max_element(all(r1))-r1.begin();
      |       ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
towns.cpp:64:18: warning: declaration of 'mp' shadows a global declaration [-Wshadow]
   64 |     map<int,int> mp;
      |                  ^~
towns.cpp:21:14: note: shadowed declaration is here
   21 | map<pii,int> mp;
      |              ^~
towns.cpp:37:11: warning: variable 'u' set but not used [-Wunused-but-set-variable]
   37 |     int v,u;
      |           ^
towns.cpp:104:9: warning: unused variable 'ok' [-Wunused-variable]
  104 |     int ok=0;
      |         ^~

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