oj.uz

Submission #714918

# Submission time Handle Problem Language Result Execution time Memory
714918 2023-03-25T13:20:10 Z ibrahim001 Stranded Far From Home (BOI22_island) C++14
40 / 100
 1000 ms 29120 KB 
#include "bits/stdc++.h"
#define intt long long
#define pb push_back
#define endl '\n'
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<intt,intt>
#define ld long double
using namespace std;
const int sz = 2e5+5;
int a[sz];
vector<int>g[sz];
set<int>s;
int used[sz];
string res;
intt dfs(int node, int mx){
    used[node] = mx;
    intt res = a[node];
    for ( int i : g[node] ){
        if ( a[i] < mx and used[i] != mx ) res += dfs(i, mx);
    }
    return res;
}
void fill(int node, int mx){
    res[node-1] = '0';
    for ( int i : g[node] ){
        if ( a[i] < mx and res[i-1] == '1' ){
            fill(i, mx);
        }
    }
}
int i,j;
int main(){
    int n, m;
    cin >> n >> m;
    res.resize(n, '1');
    for ( i = 1; i <= n; i++ ){
        cin >> a[i];
        s.insert(a[i]);
    }
    for ( i = 1; i <= m; i++ ){
        int x, y;
        cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    while (!s.empty()){
        int mx = *s.rbegin();
        s.erase(mx);
        for ( i = 1; i <= n; i++ ){
            if ( a[i] < mx and res[i-1] == '1' and used[i] != mx and dfs(i, mx) < 1LL*mx ){
                fill(i, mx);
            }
        }
    }
    cout << res << endl;
}
/*
4 3 
4 2 2 1 
1 2
3 2
4 1
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 35 ms 5076 KB Output is correct
5 Correct 30 ms 5164 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 27 ms 5076 KB Output is correct
8 Correct 26 ms 5160 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Correct 31 ms 5232 KB Output is correct
11 Correct 36 ms 5204 KB Output is correct
12 Correct 22 ms 5120 KB Output is correct
13 Correct 4 ms 5076 KB Output is correct
14 Correct 7 ms 5076 KB Output is correct

Subtask #2
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 Execution timed out 1066 ms 27408 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 1070 ms 29120 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 361 ms 13300 KB Output is correct
3 Correct 351 ms 17624 KB Output is correct
4 Correct 394 ms 17784 KB Output is correct
5 Correct 245 ms 16920 KB Output is correct
6 Correct 264 ms 16484 KB Output is correct
7 Correct 235 ms 18372 KB Output is correct
8 Correct 203 ms 22760 KB Output is correct
9 Correct 226 ms 12864 KB Output is correct
10 Correct 271 ms 16168 KB Output is correct
11 Correct 328 ms 27420 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 35 ms 5076 KB Output is correct
5 Correct 30 ms 5164 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 27 ms 5076 KB Output is correct
8 Correct 26 ms 5160 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Correct 31 ms 5232 KB Output is correct
11 Correct 36 ms 5204 KB Output is correct
12 Correct 22 ms 5120 KB Output is correct
13 Correct 4 ms 5076 KB Output is correct
14 Correct 7 ms 5076 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Execution timed out 1066 ms 27408 KB Time limit exceeded
18 Halted 0 ms 0 KB -