oj.uz

Submission #714632

# Submission time Handle Problem Language Result Execution time Memory
714632 2023-03-25T06:50:14 Z Khizri Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 16344 KB 
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
//------------------------------DEFINE------------------------------
//******************************************************************
#define IOS ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0)
#define ll long long
#define int long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
#define endl "\n"
//******************************************************************
//----------------------------FUNCTION------------------------------
//******************************************************************
ll gcd(ll a,ll b){
    if(a>b) swap(a,b);
    if(a==0) return a+b;
    return gcd(b%a,a);
}
ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}
bool is_prime(ll n){
    ll k=sqrt(n);

    if(n==2) return true;
    if(n<2||n%2==0||k*k==n) return false;
    for(int i=3;i<=k;i+=2){
        if(n%i==0){
            return false;
        }
    }
    return true;
}
//*****************************************************************
//--------------------------MAIN-CODE------------------------------
const int mxn=2e5+5;
int t=1,n,m,arr[mxn];
vector<int>vt[mxn];
bool f(int a,int b){
    return arr[a]<arr[b];
}
bool check(int u){
    priority_queue<pii,vector<pii>,greater<pii>>q;
    ll ans=arr[u];
    for(int v:vt[u]){
        q.push({arr[v],v});
    }
    vector<int>color(n+5);
    color[u]=1;
    while(q.size()){
        pii p=q.top();
        q.pop();
        int u=p.S;
        ll sum=p.F;
        if(color[u]) continue;
        if(sum>ans) return false;
        ans+=sum;
        color[u]=1;
        for(int v:vt[u]){
            if(!color[v]){
                q.push({arr[v],v});
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(!color[i]) return false;
    }
    return true;
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    while(m--){
        int a,b;
        cin>>a>>b;
        vt[a].pb(b);
        vt[b].pb(a);
    }
    for(int i=1;i<=n;i++){
        if(check(i)){
            cout<<1;
        }
        else{
            cout<<0;
        }
    }
    cout<<endl;
}
signed main(){
    IOS;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5016 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 201 ms 5136 KB Output is correct
5 Correct 149 ms 5136 KB Output is correct
6 Correct 327 ms 5196 KB Output is correct
7 Correct 212 ms 5148 KB Output is correct
8 Correct 171 ms 5132 KB Output is correct
9 Correct 215 ms 5160 KB Output is correct
10 Correct 66 ms 5076 KB Output is correct
11 Correct 63 ms 5132 KB Output is correct
12 Correct 62 ms 5148 KB Output is correct
13 Correct 116 ms 5076 KB Output is correct
14 Correct 96 ms 5136 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5024 KB Output is correct
3 Execution timed out 1070 ms 16344 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 1083 ms 14288 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 1070 ms 15592 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5016 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 201 ms 5136 KB Output is correct
5 Correct 149 ms 5136 KB Output is correct
6 Correct 327 ms 5196 KB Output is correct
7 Correct 212 ms 5148 KB Output is correct
8 Correct 171 ms 5132 KB Output is correct
9 Correct 215 ms 5160 KB Output is correct
10 Correct 66 ms 5076 KB Output is correct
11 Correct 63 ms 5132 KB Output is correct
12 Correct 62 ms 5148 KB Output is correct
13 Correct 116 ms 5076 KB Output is correct
14 Correct 96 ms 5136 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 5024 KB Output is correct
17 Execution timed out 1070 ms 16344 KB Time limit exceeded
18 Halted 0 ms 0 KB -