Submission #602729

#	Time	Username	Problem	Language	Result	Execution time	Memory
602729		isaachew	Stranded Far From Home (BOI22_island)	C++17	20 / 100	510 ms	24292 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?)
 
 Subtree sums +
 ST3: Line
 The only shape an area can make is a segment
 ST4:
 Two neighbouring villages with the same population can be treated exactly the same
 
 35p?
 */
int n,m;
std::vector<std::vector<int>> edges;
std::vector<int> pops;
std::vector<long long> sts;
std::vector<int> result;

long long dfs(int cur){
    long long csts=pops[cur];
    for(int i:edges[cur]){
        if(i<cur)continue;
        csts+=dfs(i);
    }
    sts[cur]=csts;
    return csts;
}
void dfs2(int cur){
    result[cur]=1;
    for(int i:edges[cur]){
        if(i<cur)continue;
        if(sts[i]>=pops[cur])dfs2(i);
    }
}

int main(){
    std::cin>>n>>m;
    edges.resize(n);
    result.resize(n,0);
    for(int i=0;i<n;i++){
        int x;
        std::cin>>x;
        pops.push_back(x);
    }
    bool st3=1;
    for(int i=0;i<m;i++){
        int a,b;
        std::cin>>a>>b;
        a--,b--;
        if(a-b>1||a-b<-1)st3=0;
        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;
    }
    if(0&&st3){
        
    }else{
        
        sts.resize(n,0);
        dfs(0);
        dfs2(0);
    }
    for(int i:result){
        std::cout<<i;
    }
    std::cout<<'\n';
}

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