oj.uz

Submission #587112

# Submission time Handle Problem Language Result Execution time Memory
587112 2022-07-01T10:39:04 Z BT21tata Stranded Far From Home (BOI22_island) C++17
10 / 100
 390 ms 852 KB 
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define SPEED ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0)
#define rall(v) (v).rbegin(),(v).rend()
#define all(v) (v).begin(),(v).end()
#define setp fixed<<setprecision
#define OK cerr<<"OK"<<endl<<flush
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define F first
#define S second
#define y0 jahdakdh
#define y1 jahsadakdakdh
#define endl '\n'
const ll MOD=1e9+7;
const ll mod=(1ll<<31)-1;
const ld eps=1e-8;
using namespace std;
mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());

int n, m;
ll cnt[20005];
vector<int>g[2005];
bool used[2005];

int main()
{
    SPEED;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        cin>>cnt[i];
    for(int i=0; i<m; i++)
    {
        int u, v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    for(int i=1; i<=n; i++)
    {
        ll cur=cnt[i];
        multiset<pii>s;
        bool pos=1;
        memset(used, 0, sizeof(used));
        for(int u : g[i])
            s.insert({cnt[u], u});
        used[i]=1;
        while(s.size())
        {
            int q=(*s.begin()).S; s.erase(s.begin());
           // cout<<q<<' '<<cnt[q]<<' '<<cur<<endl;
            if(used[q]) continue;
            if(cnt[q]>cur)
            {
                break;
            }
            used[q]=1;
            cur+=cnt[q];
            for(int u : g[q])
            {
            //    cout<<"push  "<<q<<' '<<u<<' '<<cnt[u]<<endl;
                if(!used[u]) s.insert({cnt[u], u});
            }
        }
        for(int i=1; i<=n; i++)
            if(!used[i]) pos=0;
        cout<<pos;
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 260 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 242 ms 468 KB Output is correct
5 Correct 181 ms 468 KB Output is correct
6 Correct 390 ms 468 KB Output is correct
7 Correct 251 ms 468 KB Output is correct
8 Correct 191 ms 444 KB Output is correct
9 Correct 348 ms 488 KB Output is correct
10 Correct 96 ms 448 KB Output is correct
11 Correct 91 ms 340 KB Output is correct
12 Correct 107 ms 444 KB Output is correct
13 Correct 201 ms 468 KB Output is correct
14 Correct 102 ms 340 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Runtime error 3 ms 852 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Runtime error 5 ms 792 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Runtime error 3 ms 852 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 260 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 242 ms 468 KB Output is correct
5 Correct 181 ms 468 KB Output is correct
6 Correct 390 ms 468 KB Output is correct
7 Correct 251 ms 468 KB Output is correct
8 Correct 191 ms 444 KB Output is correct
9 Correct 348 ms 488 KB Output is correct
10 Correct 96 ms 448 KB Output is correct
11 Correct 91 ms 340 KB Output is correct
12 Correct 107 ms 444 KB Output is correct
13 Correct 201 ms 468 KB Output is correct
14 Correct 102 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Runtime error 3 ms 852 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -