제출 #1160516

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160516		jus_teng	9월 (APIO24_september)	C++20	컴파일 에러	0 ms	0 KiB

september

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

typedef long long ll;

// Build the tree as an adjacency list from the parent array
vector<vector<ll>> buildTree(ll numberOfNodes, vector<ll>& parent) {
    vector<vector<ll>> adjacencyList(numberOfNodes);
    for (ll i = 1; i < numberOfNodes; i++) {
        adjacencyList[parent[i]].push_back(i);
    }
    return adjacencyList;
}

// Use DFS to find all leaf nodes
void findLeaves(ll node, vector<vector<ll>>& adjacencyList, vector<ll>& leaves) {
    if (adjacencyList[node].empty() && node != 0) {
        leaves.push_back(node);
    }
    for (ll child : adjacencyList[node]) {
        findLeaves(child, adjacencyList, leaves);
    }
}

// Solve for the maximum number of days
int solve(ll numberOfNodes, ll numberOfVolunteers, vector<ll> parent, vector<vector<ll>> volunteerRecords) {
    // Build the tree
    vector<vector<ll>> adjacencyList = buildTree(numberOfNodes, parent);
    
    // Find all leaves
    vector<ll> leaves;
    findLeaves(0, adjacencyList, leaves);
    sort(leaves.begin(), leaves.end());
    
    // Special case: 0 or 1 leaf
    if (leaves.size() <= 1) return leaves.size();
    
    ll maxDays = 0;
    
    // Try all permutations of leaf falling order
    do {
        // Initialize queues for each volunteer's record
        vector<queue<ll>> sequences(numberOfVolunteers);
        for (ll i = 0; i < numberOfVolunteers; i++) {
            for (ll j = 0; j < volunteerRecords[i].size(); j++) {
                sequences[i].push(volunteerRecords[i][j]);
            }
        }
        
        ll currentDay = 1; // Start with day 1
        bool isValid = true;
        
        // Process each leaf in the current order
        for (ll i = 0; i < leaves.size(); i++) {
            bool found = false;
            for (ll vol = 0; vol < numberOfVolunteers; vol++) {
                if (!sequences[vol].empty() && sequences[vol].front() == leaves[i]) {
                    sequences[vol].pop();
                    found = true;
                    break;
                }
            }
            if (!found) {
                currentDay++; // New day if no volunteer expected this leaf
            }
        }
        
        // Check if all records are fully used
        for (ll vol = 0; vol < numberOfVolunteers; vol++) {
            if (!sequences[vol].empty()) {
                isValid = false;
                break;
            }
        }
        
        // Update maximum days if this order is valid
        if (isValid) {
            maxDays = max(maxDays, currentDay);
        }
    } while (next_permutation(leaves.begin(), leaves.end()));
    
    return maxDays;
}

// Main function to handle multiple test cases
int main() {
    ll testCases;
    scanf("%lld", &testCases);
    while (testCases--) {
        ll numberOfNodes, numberOfVolunteers;
        scanf("%lld %lld", &numberOfNodes, &numberOfVolunteers);
        
        // Read the parent array
        vector<ll> parent(numberOfNodes);
        parent[0] = -1; // Root has no parent
        for (ll i = 1; i < numberOfNodes; i++) {
            scanf("%lld", &parent[i]);
        }
        
        // Read volunteers' records
        vector<vector<ll>> volunteerRecords(numberOfVolunteers);
        for (ll i = 0; i < numberOfVolunteers; i++) {
            volunteerRecords[i].resize(numberOfNodes - 1); // Max possible leaves
            for (ll j = 0; j < numberOfNodes - 1; j++) {
                scanf("%lld", &volunteerRecords[i][j]);
            }
        }
        
        // Get and print the result
        ll result = solve(numberOfNodes, numberOfVolunteers, parent, volunteerRecords);
        printf("%lld\n", result);
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

september.cpp: In function 'int main()':
september.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     scanf("%lld", &testCases);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
september.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         scanf("%lld %lld", &numberOfNodes, &numberOfVolunteers);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
september.cpp:97:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |             scanf("%lld", &parent[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~
september.cpp:105:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |                 scanf("%lld", &volunteerRecords[i][j]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccCwTvHU.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cciEHuTR.o:september.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccCwTvHU.o: in function `mtbpdhr2zxjo1o4i9oreohsbuzzl4s6u::taskcase()':
grader.cpp:(.text+0x50d): undefined reference to `solve(int, int, std::vector<int, std::allocator<int> >, std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >)'
collect2: error: ld returned 1 exit status