oj.uz

Submission #602568

# Submission time Handle Problem Language Result Execution time Memory
602568 2022-07-23T08:47:34 Z isaachew Stranded Far From Home (BOI22_island) C++17
10 / 100
 499 ms 15296 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 282 ms 428 KB Output is correct
5 Correct 289 ms 424 KB Output is correct
6 Correct 423 ms 420 KB Output is correct
7 Correct 327 ms 424 KB Output is correct
8 Correct 238 ms 424 KB Output is correct
9 Correct 499 ms 480 KB Output is correct
10 Correct 111 ms 436 KB Output is correct
11 Correct 122 ms 444 KB Output is correct
12 Correct 171 ms 440 KB Output is correct
13 Correct 249 ms 424 KB Output is correct
14 Correct 154 ms 432 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 244 ms 14188 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 243 ms 15296 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Incorrect 248 ms 15224 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 282 ms 428 KB Output is correct
5 Correct 289 ms 424 KB Output is correct
6 Correct 423 ms 420 KB Output is correct
7 Correct 327 ms 424 KB Output is correct
8 Correct 238 ms 424 KB Output is correct
9 Correct 499 ms 480 KB Output is correct
10 Correct 111 ms 436 KB Output is correct
11 Correct 122 ms 444 KB Output is correct
12 Correct 171 ms 440 KB Output is correct
13 Correct 249 ms 424 KB Output is correct
14 Correct 154 ms 432 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Incorrect 244 ms 14188 KB Output isn't correct
18 Halted 0 ms 0 KB -