Submission #1160509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160509		jus_teng	Village (BOI20_village)	C++20	12 / 100	35 ms	836 KiB

Village

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

typedef long long ll;

/*BFS algorithm adapted from https://cp-algorithms.com/graph/breadth-first-search.html
Modifications:
- `vector<bool> visited` to track visited nodes
- Initialized `vector<ll> distanceFromStart(numberOfHouses + 1, 0)` to 0 and not -1
- Initialized `queue<ll> q` with start node and marked as visited
- `distanceFromStart[v] = distanceFromStart[u] + 1` to update distances
*/

vector<vector<ll>> BFSAlgo(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, 0);
        vector<bool> visited(numberOfHouses + 1, false);
        queue<ll> q;

        q.push(startHouse);
        visited[startHouse] = true;

        while (!q.empty()){
            
            ll currentHouse = q.front();
            q.pop();

            for (ll nextHouse : adjacencyList[currentHouse]){
                
                if (!visited[nextHouse]){
                    
                    visited[nextHouse] = true;
                    q.push(nextHouse);
                    distanceFromStart[nextHouse] = distanceFromStart[currentHouse] + 1;
                }
            }
        }

        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 = BFSAlgo(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:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%lld", &numberOfHouses);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Village.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         scanf("%lld %lld", &houseA, &houseB);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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