oj.uz

Submission #714800

# Submission time Handle Problem Language Result Execution time Memory
714800 2023-03-25T09:44:06 Z Ferid20072020 Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 34056 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 = 2e5 + 3;
int n , m;
int tot[MAX];
vv(vv(int)) g(MAX);
vv(vv(pii)) g1(MAX);
vv(int) color(MAX);
vv(int) level(MAX);
vv(int) pref(MAX);
vv(int) parent(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 : g1[src]){
        if(color[to.s] == 0 && to.f <= total){
            cnt++;
            total += to.f;
            DFS(to.s);
        }
    }
}

void DFS1(int src , int lvl){
    level[src] = lvl;
    for(auto to : g[src]){
        if(to > src){
            parent[to] = src;
            DFS1(to , lvl+1);
        }
    }
}

void solve(){
    int Max = -1e9;
    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;
            g1[u].pb({tot[v] , v});
            g1[v].pb({tot[u] , u});
        }
        for(int i=1 ; i<=n ; i++){
            sort(all(g1[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;
}

Compilation message

island.cpp: In function 'void solve()':
island.cpp:81:9: warning: unused variable 'Max' [-Wunused-variable]
   81 |     int Max = -1e9;
      |         ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 9 ms 15956 KB Output is correct
3 Correct 8 ms 16052 KB Output is correct
4 Correct 115 ms 16068 KB Output is correct
5 Correct 125 ms 16108 KB Output is correct
6 Correct 128 ms 16084 KB Output is correct
7 Correct 117 ms 16116 KB Output is correct
8 Correct 92 ms 16104 KB Output is correct
9 Correct 131 ms 16156 KB Output is correct
10 Correct 119 ms 16168 KB Output is correct
11 Correct 114 ms 16168 KB Output is correct
12 Correct 105 ms 16128 KB Output is correct
13 Correct 148 ms 16164 KB Output is correct
14 Correct 118 ms 16104 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Execution timed out 1067 ms 30756 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Execution timed out 1080 ms 34056 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Execution timed out 1069 ms 28712 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 9 ms 15956 KB Output is correct
3 Correct 8 ms 16052 KB Output is correct
4 Correct 115 ms 16068 KB Output is correct
5 Correct 125 ms 16108 KB Output is correct
6 Correct 128 ms 16084 KB Output is correct
7 Correct 117 ms 16116 KB Output is correct
8 Correct 92 ms 16104 KB Output is correct
9 Correct 131 ms 16156 KB Output is correct
10 Correct 119 ms 16168 KB Output is correct
11 Correct 114 ms 16168 KB Output is correct
12 Correct 105 ms 16128 KB Output is correct
13 Correct 148 ms 16164 KB Output is correct
14 Correct 118 ms 16104 KB Output is correct
15 Correct 8 ms 15956 KB Output is correct
16 Correct 8 ms 15956 KB Output is correct
17 Execution timed out 1067 ms 30756 KB Time limit exceeded
18 Halted 0 ms 0 KB -