oj.uz

Submission #710733

# Submission time Handle Problem Language Result Execution time Memory
710733 2023-03-15T17:21:40 Z sysia Stranded Far From Home (BOI22_island) C++17
10 / 100
 527 ms 64180 KB 
//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;

struct DSU{
    vector<int>rep, sz;
    vector<bool>ans;
    vector<vector<int>>tab;

    void clear(int v){
        v = f(v);
        for (auto x: tab[v]){
            ans[x] = 0;
        }
        tab[v].clear();
    }

    DSU(int n, vector<int>&a){
        rep.assign(n+1, 0);
        tab.resize(n+1);
        ans.assign(n+1, 1);
        for (int i = 1; i<=n; i++) tab[i].emplace_back(i);
        iota(rep.begin(), rep.end(), 0);
        sz = a;
    }

    int f(int a){return a == rep[a] ? a : rep[a] = f(rep[a]);}

    bool u(int a, int b){
        a = f(a);b = f(b);
        if (a == b) return 0;
        if ((int)tab[a].size() < (int)tab[b].size()) swap(a, b);
        for (auto x: tab[b]) tab[a].emplace_back(x);
        tab[b].clear();
        sz[a] += sz[b];
        rep[b] = a;
        return 1;
    }

};

void solve(){
    int n, m; cin >> n >> m;
    vector<int>a(n+1);
    map<int, vector<int>>event;
    for (int i = 1; i<=n; i++) {
        cin >> a[i];
        event[a[i]].emplace_back(i);
    }
    vector<T>edges;
    vector<vector<int>>g(n+1);
    for (int i = 0; i<m; i++) {
        int a, b; cin >> a >> b;
        edges.emplace_back(a, b);
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    sort(edges.begin(), edges.end(), [&](auto x, auto y){
        return max(a[x.first], a[x.second]) < max(a[y.first], a[y.second]);
    });
    DSU dsu(n+2, a);
    int ptr = -1;
    for (auto [w, curr]: event){
        while (ptr+1 < (int)edges.size() && max(a[edges[ptr+1].first], a[edges[ptr+1].second]) <= w) {
            ptr++;
            debug(edges[ptr]);
            dsu.u(edges[ptr].first, edges[ptr].second);
        }
        for (auto v: curr){
            for (auto x: g[v]){
                debug(v, x, dsu.sz[dsu.f(v)], dsu.sz[dsu.f(x)]);
                if (a[x] > a[v] && dsu.sz[dsu.f(v)] < dsu.sz[dsu.f(x)]){
                    dsu.clear(v);
                }
            }
        }
    }
    for (int i = 1; i<=n; i++) cout << (dsu.ans[i] ? 1 : 0);
    cout << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 2 ms 724 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 259 ms 56048 KB Output is correct
4 Correct 262 ms 49472 KB Output is correct
5 Correct 296 ms 62064 KB Output is correct
6 Correct 293 ms 59352 KB Output is correct
7 Correct 311 ms 64180 KB Output is correct
8 Correct 271 ms 50188 KB Output is correct
9 Correct 270 ms 62908 KB Output is correct
10 Correct 188 ms 52372 KB Output is correct
11 Correct 169 ms 42028 KB Output is correct
12 Correct 286 ms 40580 KB Output is correct
13 Correct 208 ms 53220 KB Output is correct
14 Correct 214 ms 51504 KB Output is correct
15 Correct 271 ms 60220 KB Output is correct
16 Correct 183 ms 59008 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 527 ms 59864 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 243 ms 36972 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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