Submission #1084920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084920		dosts	Stranded Far From Home (BOI22_island)	C++17	0 / 100	209 ms	38628 KiB

island

//Dost SEFEROĞLU
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
#define ordered_set tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update>
const int MOD = 1e9+7,inf = 2e18;
const int N = 1e6+50;

struct DSU {
    int n;
    vi dad,sm,sz;
    stack<int> st;
    DSU(int nn) {
        n = nn;
        dad.resize(n+1);
        iota(all(dad),0ll);
        sm.assign(n+1,0),sz.assign(n+1,1);
    }
    void unite(int a,int b) {
        int x = find(a),y = find(b);
        if (x == y) {
            st.push(-1);
            return;
        }
        if (sz[x] < sz[y]) swap(x,y);
        st.push(y);
        dad[y] = x;
        sm[x]+=sm[y];
        sz[x]+=sz[y];
    }
    int find(int x) {
        if (x == dad[x]) return x;
        return find(dad[x]);
    }
    void rollback() {
        assert(!st.empty());
        if (st.top() == -1) {
            st.pop();
            return;
        }
        sm[dad[st.top()]]-=sm[st.top()];
        sz[dad[st.top()]]-=sz[st.top()];
        dad[st.top()] = st.top();
        st.pop();
    }
};

void solve() {
    int n,m;
    cin >> n >> m;
    map<int,vector<pii>> edg;
    vi w(n+1);
    for (int i=1;i<=n;i++) cin >> w[i];
    for (int i=1;i<=m;i++) {
        int a,b;
        cin >> a >> b;
        edg[max(w[a],w[b])].push_back({a,b});
    }
    vi ans(n+1,0);
    vector<pii> ps(n+1);
    for (int i=1;i<=n;i++) ps[i] = {w[i],i};
    DSU dsu(n);
    for (int i=1;i<=n;i++) dsu.sm[i] = w[i];
    sort(ps.begin()+1,ps.end(),greater<pii>());
    for (int i=n;i>=1;i--) {
        if (i == n || ps[i].ff != ps[i+1].ff) {
            for (auto it : edg[ps[i].ff]) {
                dsu.unite(it.ff,it.ss);
            }
        }
    }
    int req = 0;
    for (int i=1;i<=n;i++) {
        if (i != 1 && ps[i-1].ff != ps[i].ff) {
            for (auto& it : edg[ps[i-1].ff]) dsu.rollback();
            req = ps[i-1].ff;
        }
        if (dsu.sm[dsu.find(ps[i].ss)] >= req) ans[ps[i].ss] = 1;
    }
    for (int i=1;i<=n;i++) cout << ans[i];
    cout << endl;
}                    
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

Compilation message (stderr)

island.cpp: In function 'void solve()':
island.cpp:83:24: warning: unused variable 'it' [-Wunused-variable]
   83 |             for (auto& it : edg[ps[i-1].ff]) dsu.rollback();
      |                        ^~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35