Submission #676384

#	Time	Username	Problem	Language	Result	Execution time	Memory
676384		flashhh	Railway (BOI17_railway)	C++17	100 / 100	201 ms	42196 KiB

railway

#include <bits/stdc++.h>

using namespace std;

int numVertices, numPlans, minimumPlans;
vector<int> acceptedEdges;
vector<int> numVerticesOnPlan;
vector<vector<int> > plansOfVertice;
vector<vector<pair<int,int> > > adj;

void Read() {
    cin >> numVertices >> numPlans >> minimumPlans;

    numVerticesOnPlan.resize(numPlans);
    adj.resize(numVertices);
    plansOfVertice.resize(numVertices);
    
    for (int numEdge = 0; numEdge < numVertices - 1; ++numEdge) {
        int u,v; cin >> u >> v;
        --u; --v;

        adj[u].emplace_back(numEdge, v);
        adj[v].emplace_back(numEdge, u);
    }

    for (int numPlan = 0; numPlan < numPlans; ++numPlan) {
        int planQuantity; cin >> planQuantity;
        
        numVerticesOnPlan[numPlan] = planQuantity;

        while (planQuantity--) {
            int vertice; cin >> vertice;
            --vertice;

            plansOfVertice[vertice].push_back(numPlan);
        }
    }
}

void calculate() {
    vector<map<int,int> > myMap;

    myMap.resize(numVertices);

    auto dfs = [&] (int u, int cha, int prevEdge, auto&& dfs) -> void {
        for (int plan : plansOfVertice[u]) ++myMap[u][plan];

        for (auto [numEdge, v] : adj[u]) {
            if (v == cha) continue;
            dfs(v, u, numEdge, dfs);

            if (myMap[u].size() < myMap[v].size()) swap(myMap[u], myMap[v]);

            for (map<int,int> :: iterator it = myMap[v].begin(); it != myMap[v].end(); ++it) {
                int plan = it -> first; int quantity = it -> second;

                myMap[u][plan] += quantity;
                if (myMap[u][plan] == numVerticesOnPlan[plan]) myMap[u].erase(plan);
            }
        }
        
        if (myMap[u].size() >= minimumPlans) acceptedEdges.push_back(prevEdge);
    };

    dfs(0, -1, -1, dfs);

    sort(acceptedEdges.begin(), acceptedEdges.end());

    cout << acceptedEdges.size() <<'\n';
    for (auto numEdge : acceptedEdges) cout << numEdge + 1 <<" "; cout <<'\n';
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    Read();
    calculate();

    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void calculate()':
railway.cpp:70:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   70 |     for (auto numEdge : acceptedEdges) cout << numEdge + 1 <<" "; cout <<'\n';
      |     ^~~
railway.cpp:70:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   70 |     for (auto numEdge : acceptedEdges) cout << numEdge + 1 <<" "; cout <<'\n';
      |                                                                   ^~~~
railway.cpp: In instantiation of 'calculate()::<lambda(int, int, int, auto:23&&)> [with auto:23 = calculate()::<lambda(int, int, int, auto:23&&)>&]':
railway.cpp:65:23:   required from here
railway.cpp:62:29: warning: comparison of integer expressions of different signedness: 'std::map<int, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |         if (myMap[u].size() >= minimumPlans) acceptedEdges.push_back(prevEdge);
      |             ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25