oj.uz

Submission #714688

# Submission time Handle Problem Language Result Execution time Memory
714688 2023-03-25T07:54:59 Z Ferid20072020 Stranded Far From Home (BOI22_island) C++14
10 / 100
 64 ms 732 KB 
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
 
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll          long long 
#define ull         unsigned long long 
#define ld          long double 
#define ui          unsigned int 
#define f           first
#define s           second
#define ins         insert
#define pb          push_back
#define mp          make_pair
#define ln          '\n'
#define int         ll
#define pii         pair<int , int> 
#define INF         LLONG_MAX
#define vv(a)       vector<a>
#define pp(a, b)    pair<a, b>
#define pq(a)       priority_queue<a>
#define qq(a)       queue<a>
#define ss(a)       set<a>
#define mss(a)      multiset<a>
#define mm(a, b)    map<a, b>
#define mmm(a , b)  multimap<a , b>
#define sz(x)       (x).size()
#define all(x)      (x).begin() , (x).end()
#define fastio                    \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
 
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
const int MAX = 2005;
int n , m;
vv(vv(pii)) g(MAX);
vv(int) tot(MAX);
vv(int) color(MAX);
int cnt = 0 , total = 0;

void init(){
    cnt = 1;
    total = 0;
    for(int i=1 ; i<MAX ; i++){
        color[i] = 0;
    }
}

void DFS(int src){
    //cout << src << ln;
    color[src] = 1;
    for(auto to : g[src]){
        if(color[to.s] == 0 && to.f <= total){
            cnt++;
            total += to.f;
            DFS(to.s);
        }
    }
}
 
void solve(){
    cin >> n >> m;
    for(int i=1 ; i<=n ; i++){
        cin >> tot[i];
    }
    for(int i=0 ; i<m ; i++){
        int u , v;
        cin >> u >> v;
        g[u].pb({tot[v] , v});
        g[v].pb({tot[u] , u});
    }
    for(int i=1 ; i<=n ; i++){
        sort(all(g[i]));
    }
    for(int i=1 ; i<=n ; i++){
        init();
        total = tot[i];
        DFS(i);
        while(cnt < n){
            int cnt1 = cnt;
            for(int j=1 ; j<=n ; j++){
                if(color[j] == 1){
                    DFS(j);
                }
            }
            if(cnt == cnt1){
                break;
            }
        }
        if(cnt == n){
            cout << 1;
        }
        else{
            cout << 0;
        }
    }
}
 
 
signed main(){
    fastio
 
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
 
    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 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 43 ms 520 KB Output is correct
5 Correct 39 ms 468 KB Output is correct
6 Correct 63 ms 504 KB Output is correct
7 Correct 44 ms 468 KB Output is correct
8 Correct 31 ms 468 KB Output is correct
9 Correct 41 ms 512 KB Output is correct
10 Correct 36 ms 468 KB Output is correct
11 Correct 35 ms 560 KB Output is correct
12 Correct 22 ms 524 KB Output is correct
13 Correct 64 ms 568 KB Output is correct
14 Correct 39 ms 500 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Runtime error 4 ms 724 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 0 ms 340 KB Output is correct
2 Runtime error 4 ms 732 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 4 ms 724 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 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 43 ms 520 KB Output is correct
5 Correct 39 ms 468 KB Output is correct
6 Correct 63 ms 504 KB Output is correct
7 Correct 44 ms 468 KB Output is correct
8 Correct 31 ms 468 KB Output is correct
9 Correct 41 ms 512 KB Output is correct
10 Correct 36 ms 468 KB Output is correct
11 Correct 35 ms 560 KB Output is correct
12 Correct 22 ms 524 KB Output is correct
13 Correct 64 ms 568 KB Output is correct
14 Correct 39 ms 500 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Runtime error 4 ms 724 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -