oj.uz

Submission #602721

# Submission time Handle Problem Language Result Execution time Memory
602721 2022-07-23T10:41:40 Z isaachew Stranded Far From Home (BOI22_island) C++17
10 / 100
 427 ms 20444 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?)
 
 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=1;
    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(st3){
        
    }else{
        
        sts.resize(n,0);
        dfs(0);
        dfs2(0);
    }
    for(int i:result){
        std::cout<<i;
    }
    std::cout<<'\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 276 ms 448 KB Output is correct
5 Correct 249 ms 432 KB Output is correct
6 Correct 413 ms 424 KB Output is correct
7 Correct 280 ms 476 KB Output is correct
8 Correct 212 ms 464 KB Output is correct
9 Correct 427 ms 480 KB Output is correct
10 Correct 116 ms 436 KB Output is correct
11 Correct 112 ms 468 KB Output is correct
12 Correct 145 ms 468 KB Output is correct
13 Correct 241 ms 340 KB Output is correct
14 Correct 143 ms 444 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 276 ms 448 KB Output is correct
5 Correct 249 ms 432 KB Output is correct
6 Correct 413 ms 424 KB Output is correct
7 Correct 280 ms 476 KB Output is correct
8 Correct 212 ms 464 KB Output is correct
9 Correct 427 ms 480 KB Output is correct
10 Correct 116 ms 436 KB Output is correct
11 Correct 112 ms 468 KB Output is correct
12 Correct 145 ms 468 KB Output is correct
13 Correct 241 ms 340 KB Output is correct
14 Correct 143 ms 444 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Incorrect 257 ms 20444 KB Output isn't correct
18 Halted 0 ms 0 KB -