Submission #1160502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160502		jus_teng	Village (BOI20_village)	C++20	12 / 100	49 ms	840 KiB

Village

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

typedef long long ll;

vector<vector<ll>> computeDistances(ll numberOfHouses, vector<vector<ll>>& adjacencyList){
    
    vector<vector<ll>> distances(numberOfHouses + 1, vector<ll>(numberOfHouses + 1, 0));
    
    for (ll startHouse = 1; startHouse <= numberOfHouses; startHouse++){
        
        vector<ll> distanceFromStart(numberOfHouses + 1, -1);
        queue<ll> housesToVisit;
        distanceFromStart[startHouse] = 0;
        housesToVisit.push(startHouse);
        
        while (!housesToVisit.empty()){
            
            ll currentHouse = housesToVisit.front();
            housesToVisit.pop();
            
            for (ll nextHouse : adjacencyList[currentHouse]){
                
                if (distanceFromStart[nextHouse] == -1){
                    
                    distanceFromStart[nextHouse] = distanceFromStart[currentHouse] + 1;
                    housesToVisit.push(nextHouse);
                }
            }
        }
        
        for (ll endHouse = 1; endHouse <= numberOfHouses; endHouse++){
            
            distances[startHouse][endHouse] = distanceFromStart[endHouse];
        }
    }
    
    return distances;
}

void solve(){
    
    ll numberOfHouses;
    scanf("%lld", &numberOfHouses);
    
    vector<vector<ll>> adjacencyList(numberOfHouses + 1);
    
    for (ll i = 0; i < numberOfHouses - 1; i++){
        
        ll houseA, houseB;
        scanf("%lld %lld", &houseA, &houseB);
        adjacencyList[houseA].push_back(houseB);
        adjacencyList[houseB].push_back(houseA);
    }
    
    vector<vector<ll>> distances = computeDistances(numberOfHouses, adjacencyList);
    
    if (numberOfHouses > 10){
        
        vector<ll> simpleAssignment(numberOfHouses + 1);
        
        for (ll i = 1; i <= numberOfHouses; i++){
            
            simpleAssignment[i] = (i % numberOfHouses) + 1;
        }
        
        ll totalDistance = 0;
        
        for (ll i = 1; i <= numberOfHouses; i++){
            
            totalDistance += distances[i][simpleAssignment[i]];
        }
        
        printf("%lld %lld\n", totalDistance, totalDistance);
        
        for (ll i = 1; i <= numberOfHouses; i++){
            
            printf("%lld", simpleAssignment[i]);
            
            if (i < numberOfHouses){
                
                printf(" ");
            }
            
        }
        
        printf("\n");
        
        for (ll i = 1; i <= numberOfHouses; i++){
            
            printf("%lld", simpleAssignment[i]);
            
            if (i < numberOfHouses){
                
                printf(" ");
            }
        }
        
        printf("\n");
        return;
    }
    
    vector<ll> permutation(numberOfHouses);
    
    for (ll i = 0; i < numberOfHouses; i++){
        
        permutation[i] = i + 1;
    }
    
    ll minTotalDistance = LLONG_MAX;
    ll maxTotalDistance = LLONG_MIN;
    vector<ll> minAssignment(numberOfHouses);
    vector<ll> maxAssignment(numberOfHouses);
    
    do{
        
        bool isValidMove = true;
        
        for (ll i = 0; i < numberOfHouses; i++){
            
            if (permutation[i] == i + 1){
                
                isValidMove = false;
                break;
            }
        }
        
        if (isValidMove){
            
            ll currentTotal = 0;
            
            for (ll i = 0; i < numberOfHouses; i++){
                
                currentTotal += distances[i + 1][permutation[i]];
            }
            
            if (currentTotal < minTotalDistance){
                
                minTotalDistance = currentTotal;
                minAssignment = permutation;
            }
            
            if (currentTotal > maxTotalDistance){
                
                maxTotalDistance = currentTotal;
                maxAssignment = permutation;
            }
        }
        
    } while (next_permutation(permutation.begin(), permutation.end()));
    
    printf("%lld %lld\n", minTotalDistance, maxTotalDistance);
    
    for (ll i = 0; i < numberOfHouses; i++){
        
        printf("%lld", minAssignment[i]);
        
        if (i < numberOfHouses - 1){
            
            printf(" ");
        }
    }
    
    printf("\n");
    for (ll i = 0; i < numberOfHouses; i++){
        
        printf("%lld", maxAssignment[i]);
        
        if (i < numberOfHouses - 1){
            
            printf(" ");
        }
    }
    
    printf("\n");
}

int main(){
    solve();
    return 0;
}

Compilation message (stderr)

Village.cpp: In function 'void solve()':
Village.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%lld", &numberOfHouses);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Village.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%lld %lld", &houseA, &houseB);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 0 / 38
• Subtask 3: 0 / 50