Submission #1243643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243643		moondarkside	Towns (IOI15_towns)	C++20	39 / 100	10 ms	328 KiB

towns

#include<bits/stdc++.h>
using namespace std;

int getDistance(int i,int j);

int hubDistance(int N,int sub){
    int D1=0;
    int maxD=0;
    for(int i=1;i<N;i++){
        int d=getDistance(0,i);
        if(d>maxD){
            maxD=d;
            D1=i;
        }
    }
    
    std::vector<int> Distances;
    
    maxD=0;
    int D2=0;
    for(int i=0;i<N;i++){
        int d=getDistance(D1,i);
        if(d>maxD){
            maxD=d;
            D2=i;
        }
        Distances.push_back(d);
    }
    
    int R=100000000;
    
    std::vector<int> Distances2;
    vector<int> Hubs;
    
    for(int i=0;i<N;i++){
        int d=getDistance(D2,i);
        Distances2.push_back(d);
        int k=(d+Distances[i]-maxD)/2;
        int d1=Distances[i]-k;
        int d2=d-k;
        d=max(d1,d2);
        
        if(d<R){
            Hubs.clear();
            Hubs.push_back(d1);
        }
        if(d==R && Hubs[0]!=d1 && Hubs.size()<2){
            Hubs.push_back(d1);
        }
        
        R=min(R,d);
        
    }
    
    
    vector<pair<int,int>> LRn(Hubs.size());
    vector<vector<int>> Middle(Hubs.size());
    
    for(int i=0;i<N;i++){
        int d=Distances2[i];
        int k=(d+Distances[i]-maxD)/2;
        int d1=Distances[i]-k;
        
        for(int j=0;j<Hubs.size();j++){
            if(Hubs[j]<d1){
                LRn[j].first+=1;
            }
            
            if(Hubs[j]>d1){
                LRn[j].second+=1;
            }
            
            if(Hubs[j]==d1){
                Middle[j].push_back(i);
            }
            
            
        }
        
    }

    
    for(int i=0;i<Hubs.size();i++){
        if(LRn[i].first>N/2 || LRn[i].second>N/2 || Middle[i].size()>N/2){
           
           if(LRn[i].first<=N/2 && LRn[i].second<=N/2){
            stack<int> Current;
            vector<int> Mid=Middle[i];
            for(int j=0;j<Mid.size();j++){
                if(Current.empty()){
                    Current.push(j);
                }
                else{
                    int top=Current.top();
                    int k=(Distances[top]+Distances2[top]-maxD)/2;
                    int d=getDistance(top,Mid[j]);
                    int SD=d-(Distances[Mid[j]]+d-Distances[top])/2;
                    if(SD<k){
                        Current.push(Mid[j]);
                    }
                    else{
                        Current.pop();
                    }
                    
                }
            }
            
            if(Current.empty()){
                return R;
            }
            
            int am=0;
            
            for(int j=0;j<Mid.size();j++){
                int top=Current.top();
                int k=(Distances[top]+Distances2[top]-maxD)/2;
                int d=getDistance(top,Mid[j]);
                int SD=d-(Distances[Mid[j]]+d-Distances[top])/2;
                if(SD<k){
                    am++;
                }
    
            }
             
               
            if(am>N/2){
                return -R;
            }   
            return R;
               
           }
           
        }
        else{
            return R;
        }
        
        
    }
    
    
    
    return -R;
    
    
    
}

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