oj.uz

Submission #830493

# Submission time Handle Problem Language Result Execution time Memory
830493 2023-08-19T07:15:41 Z Warinchai Stranded Far From Home (BOI22_island) C++14
10 / 100
 213 ms 13052 KB 
#include<bits/stdc++.h>
using namespace std;
long long ar[200005];
vector<int>v[200005];
int vis[200005];
int n,m;
int check(int i){
    for(int x=1;x<=n;x++){
        vis[x]=0;
    }
    priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > >pq;
    pq.push({ar[i],i});
    vis[i]=1;
    long long power=0;
    int ck=0;
    while(!pq.empty()){
        long long np=pq.top().first;
        int x=pq.top().second;
        //cout<<x<<" "<<power<<endl;
        pq.pop();
        if(x==i||power>=np){
            power+=np;
            for(int j=0;j<v[x].size();j++){
                if(vis[v[x][j]]==1){
                    continue;
                }
                vis[v[x][j]]=1;
                pq.push({ar[v[x][j]],v[x][j]});
            }
        }else{
            ck=1;
            break;
        }
    }
    if(!ck){
        return 1;
    }else{
        return 0;
    }
}
long long sum[200005];
long long mw[200005];
void dfs(int i,int p){
    long long sm=ar[i];
    for(int j=0;j<v[i].size();j++){
        if(v[i][j]==p){
            continue;
        }
        sm+=ar[v[i][j]];
    }
    sum[i]=sm;
}
void fans(int i,int p){
    if(i==1){
        mw[i]=1;
    }
    for(int j=0;j<v[i].size();j++){
        if(v[i][j]==p){
            continue;
        }
        if(sum[v[i][j]]>=sum[i]){
            mw[v[i][j]]=1;
            dfs(v[i][j],i);
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>ar[i];
    }
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    if(n>2000){
        dfs(1,0);
        fans(1,0);
        for(int i=1;i<=n;i++){
            cout<<mw[i];
        }
        return 0;
    }
    for(int i=1;i<=n;i++){
        cout<<check(i);
    }
}

Compilation message

island.cpp: In function 'int check(int)':
island.cpp:23:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |             for(int j=0;j<v[x].size();j++){
      |                         ~^~~~~~~~~~~~
island.cpp: In function 'void dfs(int, int)':
island.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int j=0;j<v[i].size();j++){
      |                 ~^~~~~~~~~~~~
island.cpp: In function 'void fans(int, int)':
island.cpp:57:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int j=0;j<v[i].size();j++){
      |                 ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 5004 KB Output is correct
4 Correct 148 ms 5112 KB Output is correct
5 Correct 138 ms 5104 KB Output is correct
6 Correct 212 ms 5104 KB Output is correct
7 Correct 147 ms 5112 KB Output is correct
8 Correct 102 ms 5088 KB Output is correct
9 Correct 213 ms 5140 KB Output is correct
10 Correct 52 ms 5104 KB Output is correct
11 Correct 54 ms 5100 KB Output is correct
12 Correct 47 ms 5076 KB Output is correct
13 Correct 93 ms 5108 KB Output is correct
14 Correct 85 ms 5076 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4972 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Incorrect 82 ms 13052 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 83 ms 12964 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 80 ms 13052 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 5004 KB Output is correct
4 Correct 148 ms 5112 KB Output is correct
5 Correct 138 ms 5104 KB Output is correct
6 Correct 212 ms 5104 KB Output is correct
7 Correct 147 ms 5112 KB Output is correct
8 Correct 102 ms 5088 KB Output is correct
9 Correct 213 ms 5140 KB Output is correct
10 Correct 52 ms 5104 KB Output is correct
11 Correct 54 ms 5100 KB Output is correct
12 Correct 47 ms 5076 KB Output is correct
13 Correct 93 ms 5108 KB Output is correct
14 Correct 85 ms 5076 KB Output is correct
15 Correct 2 ms 4972 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Incorrect 82 ms 13052 KB Output isn't correct
18 Halted 0 ms 0 KB -