oj.uz

Submission #654456

# Submission time Handle Problem Language Result Execution time Memory
654456 2022-10-31T11:00:31 Z ktkerem Stranded Far From Home (BOI22_island) C++17
40 / 100
 1000 ms 48208 KB 
#include<bits/stdc++.h>
typedef long long ll;
typedef std::pair<ll , ll> llll;
#define fi first
#define sec second
#define all(x)  x.begin() , x.end()
#define pb push_back
const ll ous = 2e5+7;
std::vector<llll> ar ;std::vector<ll> adj[ous] , nds(ous , 0) , par(ous) , sz(ous) , ans(ous , 1) , rar(ous) , kr(ous) , ant(ous);
ll n , m , o;
ll fin(ll x){
    if(par[x] == x){
        return x;
    }
    return par[x] = fin(par[x]);
}
void mrg(ll x , ll y){
    x = fin(x);y = fin(y);
    if(sz[y] > sz[x]){
        std::swap(x , y);
    }
    if(x != y){
        par[y] = x;
        sz[x] += sz[y]; 
    }
}
void dfs(ll crt){
    o += rar[crt];
    nds[crt] = 1;
    for(auto j:adj[crt]){
        if(fin(crt) != fin(j) && nds[j] == 0){
            mrg(crt , j);
            dfs(j);
        }
    }
}
void solve(){
    ll n , m;std::cin >> n >> m;
    ar.resize(n);
    for(ll i = 0;n>i;i++){
        std::cin >> ar[i].fi;
        ar[i].sec = i + 1;
        rar[i+1] = ar[i].fi;
    }
    for(ll i = 0;m>i;i++){
        ll x , y;std::cin >> x >> y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    std::sort(all(ar) , std::greater<llll>());
    ll ik = 1;
    for(;n > ik;ik++){
        if(ar[ik].fi != ar[ik-1].fi){
            break;
        }
    }
    while(n > ik){
        for(ll i = 0;n>=i;i++){
            par[i] = i;
            sz[i] = 1;
            nds[i] = 0;
            kr[i] = 0;
            ant[i] = 0;
        }
        for(ll i = 0;ik>i;i++){
            nds[ar[i].sec] = 1; 
        }
        for(ll i = ik;n>i;i++){
            ans[ar[i].sec] = 0;
        }
        for(ll i = 1;n>=i;i++){
            if(nds[i] == 0){
                dfs(i);
                kr[fin(i)] += o;
                o = 0;
            }
        }
        for(ll i = 0;ik>i;i++){
            for(auto j:adj[ar[i].sec]){
                ll ff = fin(j);
                if(kr[ff] >= ar[i].fi){
                    ant[ff] |= ans[ar[i].sec];
                }
            }
        }
        for(ll i = 1;n>=i;i++){
            ans[i] |= ant[fin(i)];
            //std::cout << ans[i] << " ";
        }
       // std::cout <<"\n\n\n";
        ik++;
        for(;n > ik;ik++){
            if(ar[ik-1].fi != ar[ik].fi){
                break;
            }
        }
    }
    for(ll i = 1;n>=i;i++){
        std::cout << ans[i];
    }
    std::cout <<"\n";

}
signed main(){
    std::ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

Subtask #1
10.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 Correct 9 ms 15984 KB Output is correct
4 Correct 132 ms 16144 KB Output is correct
5 Correct 122 ms 16084 KB Output is correct
6 Correct 8 ms 16012 KB Output is correct
7 Correct 92 ms 16184 KB Output is correct
8 Correct 83 ms 16160 KB Output is correct
9 Correct 11 ms 16188 KB Output is correct
10 Correct 112 ms 16212 KB Output is correct
11 Correct 132 ms 16272 KB Output is correct
12 Correct 86 ms 16144 KB Output is correct
13 Correct 10 ms 16212 KB Output is correct
14 Correct 20 ms 16132 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15908 KB Output is correct
2 Correct 9 ms 15960 KB Output is correct
3 Execution timed out 1099 ms 35112 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 1094 ms 37288 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 503 ms 26548 KB Output is correct
3 Correct 465 ms 26532 KB Output is correct
4 Correct 488 ms 26544 KB Output is correct
5 Correct 200 ms 26504 KB Output is correct
6 Correct 154 ms 26216 KB Output is correct
7 Correct 180 ms 27068 KB Output is correct
8 Correct 118 ms 41348 KB Output is correct
9 Correct 296 ms 26212 KB Output is correct
10 Correct 198 ms 29572 KB Output is correct
11 Correct 339 ms 48208 KB Output is correct

Subtask #5
0 / 35.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 Correct 9 ms 15984 KB Output is correct
4 Correct 132 ms 16144 KB Output is correct
5 Correct 122 ms 16084 KB Output is correct
6 Correct 8 ms 16012 KB Output is correct
7 Correct 92 ms 16184 KB Output is correct
8 Correct 83 ms 16160 KB Output is correct
9 Correct 11 ms 16188 KB Output is correct
10 Correct 112 ms 16212 KB Output is correct
11 Correct 132 ms 16272 KB Output is correct
12 Correct 86 ms 16144 KB Output is correct
13 Correct 10 ms 16212 KB Output is correct
14 Correct 20 ms 16132 KB Output is correct
15 Correct 9 ms 15908 KB Output is correct
16 Correct 9 ms 15960 KB Output is correct
17 Execution timed out 1099 ms 35112 KB Time limit exceeded
18 Halted 0 ms 0 KB -