Submission #1046953

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1046953	2024-08-07 06:50:05	isaachew	Mergers (JOI19_mergers)	C++17	100 / 100	501 ms	136360 KiB

mergers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
/*
 An edge is separable if the states on either side are disjoint
 "Unify" an entire path between edges
 Every city is a unique state -> min number of paths to cover induced tree of separable edges
 Root at "centroid" (vertex that splits leaves into sections of less than half), get leaves -> solved
 STL and look at num. distinct values to see if separable
 */
std::vector<std::vector<int>> edges;
std::vector<int> states;
std::vector<int> stamounts;
std::vector<int> parents;
std::vector<int> separable;
int nleaves=0;
std::map<int,int>* dfs(int cur,int parent=0){
    std::map<int,int>* merge=new std::map<int,int>;
    (*merge)[states[cur]]++;
    if(stamounts[states[cur]]==1){
        merge->erase(states[cur]);
    }
    for(int i:edges[cur]){
        if(i==parent)continue;
        parents[i]=cur;
        std::map<int,int>* newm=dfs(i,cur);
        if(newm->size()>merge->size())std::swap(merge,newm);
        for(std::pair<int,int> j:*newm){
            (*merge)[j.first]+=j.second;
            if((*merge)[j.first]==stamounts[j.first])merge->erase(j.first);
        }
        delete newm;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30