Submission #602568

#	Time	Username	Problem	Language	Result	Execution time	Memory
602568		isaachew	Stranded Far From Home (BOI22_island)	C++17	10 / 100	499 ms	15296 KiB

island

#include <bits/stdc++.h>
/*
 Tie colours are a connected component
 ST1: simulate with priority queue in O(n^2)
 ST2:
 Rooted tree; if a subtree manages to number more than their parent, carry on to the parent (small-to-large merging / DSU on tree)
 ST3: Line
 Calculate minimum to spread to right/left
 ST4:
 Two neighbouring villages with the same population can be treated exactly the same
 
 
 */
int n,m;
std::vector<std::vector<int>> edges;
std::vector<int> pops;
int main(){
    std::cin>>n>>m;
    edges.resize(n);
    for(int i=0;i<n;i++){
        int x;
        std::cin>>x;
        pops.push_back(x);
    }
    for(int i=0;i<m;i++){
        int a,b;
        std::cin>>a>>b;
        a--,b--;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    
    if(n<=2000&&m<=2000){
        for(int i=0;i<n;i++){
            //std::cout<<i<<'\n';
            std::set<std::pair<int,int>> pq;//priority queue but least
            std::vector<int> visited(n,0);
            long long cursize=pops[i];
            for(int j:edges[i]){
                pq.insert({pops[j],j});
            }
            visited[i]=1;
            bool result=1;
            while(!pq.empty()){
                //std::cout<<i<<' '<<cursize<<'\n';
                int cur=(*pq.begin()).second;
                pq.erase({pops[cur],cur});
                if(pops[cur]>cursize){
                    result=0;
                    break;
                }
                visited[cur]=1;
                cursize+=pops[cur];
                
                for(int j:edges[cur]){
                    if(!visited[j])pq.insert({pops[j],j});
                }
            }
            std::cout<<result;
        }
        std::cout<<'\n';
        return 0;
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35