oj.uz

Submission #602729

# Submission time Handle Problem Language Result Execution time Memory
602729 2022-07-23T10:48:11 Z isaachew Stranded Far From Home (BOI22_island) C++17
20 / 100
 510 ms 24292 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=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.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 Correct 1 ms 212 KB Output is correct
4 Correct 328 ms 412 KB Output is correct
5 Correct 279 ms 396 KB Output is correct
6 Correct 510 ms 400 KB Output is correct
7 Correct 310 ms 404 KB Output is correct
8 Correct 242 ms 392 KB Output is correct
9 Correct 510 ms 468 KB Output is correct
10 Correct 122 ms 412 KB Output is correct
11 Correct 131 ms 420 KB Output is correct
12 Correct 166 ms 340 KB Output is correct
13 Correct 270 ms 424 KB Output is correct
14 Correct 172 ms 416 KB Output is correct

Subtask #2
10.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 Correct 321 ms 18344 KB Output is correct
4 Correct 253 ms 18684 KB Output is correct
5 Correct 302 ms 14556 KB Output is correct
6 Correct 300 ms 15004 KB Output is correct
7 Correct 340 ms 15024 KB Output is correct
8 Correct 370 ms 15100 KB Output is correct
9 Correct 313 ms 14908 KB Output is correct
10 Correct 243 ms 15736 KB Output is correct
11 Correct 216 ms 15652 KB Output is correct
12 Correct 268 ms 14988 KB Output is correct
13 Correct 220 ms 24244 KB Output is correct
14 Correct 237 ms 24248 KB Output is correct
15 Correct 330 ms 24292 KB Output is correct
16 Correct 212 ms 24028 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 348 ms 23704 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 299 ms 14464 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 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 328 ms 412 KB Output is correct
5 Correct 279 ms 396 KB Output is correct
6 Correct 510 ms 400 KB Output is correct
7 Correct 310 ms 404 KB Output is correct
8 Correct 242 ms 392 KB Output is correct
9 Correct 510 ms 468 KB Output is correct
10 Correct 122 ms 412 KB Output is correct
11 Correct 131 ms 420 KB Output is correct
12 Correct 166 ms 340 KB Output is correct
13 Correct 270 ms 424 KB Output is correct
14 Correct 172 ms 416 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 321 ms 18344 KB Output is correct
18 Correct 253 ms 18684 KB Output is correct
19 Correct 302 ms 14556 KB Output is correct
20 Correct 300 ms 15004 KB Output is correct
21 Correct 340 ms 15024 KB Output is correct
22 Correct 370 ms 15100 KB Output is correct
23 Correct 313 ms 14908 KB Output is correct
24 Correct 243 ms 15736 KB Output is correct
25 Correct 216 ms 15652 KB Output is correct
26 Correct 268 ms 14988 KB Output is correct
27 Correct 220 ms 24244 KB Output is correct
28 Correct 237 ms 24248 KB Output is correct
29 Correct 330 ms 24292 KB Output is correct
30 Correct 212 ms 24028 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Incorrect 348 ms 23704 KB Output isn't correct
33 Halted 0 ms 0 KB -