oj.uz

Submission #797791

# Submission time Handle Problem Language Result Execution time Memory
797791 2023-07-29T22:44:52 Z TB_ Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 32088 KB 
#include <bits/stdc++.h>
using namespace std;

// #undef _GLIBCXX_DEBUG                // disable run-time bound checking, etc
// #pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
// #pragma GCC optimize ("unroll-loops")

// #pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
// #pragma GCC target("movbe")                                      // byte swap
// #pragma GCC target("aes,pclmul,rdrnd")                           // encryption
// #pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") // SIMD

// #include <bits/extc++.h>
// using namespace __gnu_pbds;
// template<class T>using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
// template<class T>using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long
#define INF (ll)1e9+7
#define fo(i, n) for(int i=0;i<((ll)n);i++)
#define deb(x) cout << #x << " = " << x << endl;
#define deb2(x, y) cout << #x << " = " << x << ", " << #y << " = " << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define LSOne(S) ((S) & (-S))
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
inline int readint(){ int v = 0; char c; while((c = getchar()) != EOF && c != ' ' && c != '\n'){ v *= 10; v += c - '0'; } return v; }
inline int readintsigned() { int v = 0; int sign = 1; char c = getchar(); if (c == '-') { sign = -1; } else { v += c - '0'; } while ((c = getchar()) != EOF && c != ' ' && c != '\n') { v *= 10; v += c - '0'; } return v * sign; }
inline string readstring() { string s; char c; while ((c = getchar()) != EOF && c != '\n' && c != ' ') { s.push_back(c); } return s; }
template <class result_t=std::chrono::milliseconds,class clock_t=std::chrono::steady_clock,class duration_t = std::chrono::milliseconds>
auto since(std::chrono::time_point<clock_t, duration_t> const& start){return std::chrono::duration_cast<result_t>(clock_t::now() - start);}
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vpii> vvpii;
typedef vector<vpl> vvpl;

ll n, m, val, from, to, w;
vl population;

vvl adj(200001);

struct UnionFind{
    int n;
    vl p, siz;
    UnionFind(int n) : n(n){
        p.assign(n, -1);
        siz.assign(n, 1);
        fo(i, n)p[i] = i;
    }

    int find(int x){
        if(p[x] == x) return x;
        return p[x] = find(p[x]);
    }

    void unite(int a, int b){
        a = find(a);
        b = find(b);
        if(a == b) return;
        if(siz[b] > siz[a]) swap(a, b);
        siz[a]+=siz[b];
        p[b] = a;
    }
};

int main() {
    // cout << fixed << setprecision(20);
    // auto start = std::chrono::steady_clock::now(); // since(start).count()
    cin.tie(0)->sync_with_stdio(0);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    cin >> n >> m;
    pii biggestPop = {-1, -1};
    fo(i, n){
        cin >> val;
        population.pb(val);
        biggestPop = max(biggestPop, {val, i});
    }
    fo(i, m){
        cin >> from >> to;
        adj[--from].pb(--to);
        adj[to].pb(from);
    }
    vi ans(n, -1);
    ans[biggestPop.S] = 1;

    vi order;
    fo(i, n) order.pb(i);
    shuffle(all(order), rng);

    UnionFind uf(n);

    vi seen(n, 0);
    for(auto start : order){
        start = uf.find(start);
        if(ans[start] != -1) continue;
        vi visited;
        set<pl> s = {{0, start}};

        ll currentPop = population[start];
        while(!s.empty()){
            auto res = s.lower_bound({currentPop, INF});
            if(res == s.begin()) {
                if(seen[uf.find((*res).S)]) continue;
                for(int i = 1; i < visited.size(); i++){
                    uf.unite(visited[0], visited[i]);
                }
                population[visited[0]] = currentPop;
                for(auto v : visited) seen[v] = 0;
                visited = {visited[0]};
                seen[visited[0]] = 1;
                ans[visited[0]] = 0;
                start = uf.find((*res).S);
                res++;
            }


            tie(w, to) = *--res;
            to = uf.find(to);
            s.erase(res);
            if(seen[to]) continue;
            seen[to] = 1;
            visited.pb(to);
            currentPop += w;
            if(ans[to] == 1 || currentPop >= biggestPop.F) break;
            for(auto v : adj[to])
                s.insert({population[v], v});           
        }
        ans[start] = 1;
        for(auto v : visited) seen[uf.find(v)] = 0;
    }
    fo(i, n) cout << ans[uf.find(i)];

    return 0;
}

Compilation message

island.cpp: In function 'int main()':
island.cpp:114:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |                 for(int i = 1; i < visited.size(); i++){
      |                                ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 6 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Incorrect 3 ms 5076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.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 Correct 160 ms 19724 KB Output is correct
4 Correct 124 ms 27320 KB Output is correct
5 Correct 151 ms 23540 KB Output is correct
6 Correct 163 ms 24100 KB Output is correct
7 Correct 166 ms 24100 KB Output is correct
8 Correct 165 ms 24164 KB Output is correct
9 Correct 180 ms 25372 KB Output is correct
10 Correct 119 ms 23808 KB Output is correct
11 Correct 85 ms 23656 KB Output is correct
12 Correct 177 ms 22704 KB Output is correct
13 Correct 155 ms 32088 KB Output is correct
14 Correct 106 ms 25028 KB Output is correct
15 Correct 164 ms 23108 KB Output is correct
16 Correct 376 ms 24228 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 148 ms 18684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Execution timed out 1079 ms 19452 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 6 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Incorrect 3 ms 5076 KB Output isn't correct
5 Halted 0 ms 0 KB -