Submission #1129278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129278		nhanhoang510	Stranded Far From Home (BOI22_island)	C++20	65 / 100	273 ms	30396 KiB

island

#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int maxn = 2 * 1e5 + 7;
const int LOG = 20;
const long long MOD = (long long)(1e9) + 7;
const long long base = 311;
const int ALP_BET = 26;

typedef pair<int, int> ii;
typedef pair<int, long long> il;
typedef pair<long long, int> li;
typedef pair<long long, long long> ll;

int n, m;
int a[maxn];
vector<int> adj[maxn];

namespace SUB1{

const int maxN = 2000 + 7;
bool avail[maxN];

bool getans(int st){
    memset(avail, true, sizeof(avail));
    priority_queue<ii, vector<ii>, greater<ii>> Q;
    avail[st] = false;
    for(int v : adj[st]) if(avail[v]){
        avail[v] = false;
        Q.push({a[v], v});
    }
    long long ss = a[st];
    while(!Q.empty()){
        ii tmp = Q.top();
        Q.pop();
        int w = tmp.F;
        int u = tmp.S;
        if(w > ss)
            return false;
        ss = ss + 1LL * w;
        for(int v : adj[u]) if(avail[v]){
            avail[v] = false;
            Q.push({a[v], v});
        }
    }
    return true;
}

void solve(){
    for(int i = 1; i <= n; ++i){
        bool ok = getans(i);
        if(ok == true)
            cout << 1;
        else
            cout << 0;
    }
    cout << "\n";
    return;
}

}

namespace SUB2{

bool ans[maxn];
long long sum[maxn];

void dfs_init(int u, int pa){
    sum[u] = 1LL * a[u];
    for(int v : adj[u]) if(v != pa){
        dfs_init(v, u);
        sum[u] = sum[u] + sum[v];
    }
    return;
}

void dfs(int u, int pa){
    ans[u] = true;
    for(int v : adj[u]) if(v != pa){
        if(sum[v] >= a[u]){
            dfs(v, u);
        }
    }
    return;
}

void solve(){
    dfs_init(1, 0);
    memset(ans, false, sizeof(ans));
    dfs(1, 0);
    for(int i = 1; i <= n; ++i){
        if(ans[i])
            cout << 1;
        else
            cout << 0;
    }
    cout << "\n";
    return;
}

}

namespace SUB3{

int spt[maxn][LOG];
int lg[maxn];
long long pre[maxn];

void init(){
    lg[0] = lg[1] = 0;
    for(int i = 2; i <= n; ++i)
        lg[i] = lg[i / 2] + 1;
    for(int i = 1; i <= n; ++i)
        spt[i][0] = a[i];
    for(int j = 1; j < LOG; ++j){
        for(int i = 1; i <= n; ++i){
            spt[i][j] = spt[i][j - 1];
            if(i + (1 << (j - 1)) <= n)
                spt[i][j] = max(spt[i][j], spt[i + (1 << (j - 1))][j - 1]);
        }
    }
    for(int i = 1; i <= n; ++i)
        pre[i] = pre[i - 1] + 1LL * a[i];
    return;
}

int getmax(int l, int r){
    int k = lg[r - l + 1];
    return max(spt[l][k], spt[r - (1 << k) + 1][k]);
}

bool getans(int id){
    int L = id, R = id; long long ss = a[id];
    while(L > 1 || R < n){
        bool change = false;
        int l, r, pos;
        l = 1, r = L - 1, pos = L;
        while(l <= r){
            int mid = (l + r) / 2;
            if(ss >= getmax(mid, L - 1)){
                pos = mid;
                r = mid - 1;
            } else
                l = mid + 1;
        }
        ss = ss + pre[L - 1] - pre[pos - 1];
        if(pos != L) change = true;
        L = pos;
        l = R + 1, r = n, pos = R;
        while(l <= r){
            int mid = (l + r) / 2;
            if(ss >= getmax(R + 1, mid)){
                pos = mid;
                l = mid + 1;
            } else
                r = mid - 1;
        }
        ss = ss + pre[pos] - pre[R];
        if(pos != R) change = true;
        R = pos;
        if(change == false)
            return false;
    }
    return true;
}

void solve(){
    init();
    for(int i = 1; i <= n; ++i){
        if(getans(i))
            cout << 1;
        else
            cout << 0;
    }
    cout << "\n";
    return;
}

}

namespace SUB4{

const int maxK = 10 + 7;
vector<int> xx;
vector<int> list_[maxK]; int nn;
bool ans[maxn];
bool avail[maxn];

int getid(int x){
    for(int i = 1; i <= int(xx.size()); ++i) if(xx[i - 1] == x)
        return i;
    return 1;
}

void init(){
    for(int i = 1; i <= n; ++i) xx.push_back(a[i]);
    sort(xx.begin(), xx.end());
    xx.resize(unique(xx.begin(), xx.end()) - xx.begin());
    for(int i = 1; i <= n; ++i){
        int id = getid(a[i]);
        list_[id].push_back(i);
    }
    nn = xx.size();
    return;
}

vector<int> ver;
void bfs(int st){
    ver.clear();
    queue<int> Q; Q.push(st); avail[st] = false;
    vector<int> path;
    int ss_st = a[st]; long long ss = 0;
    while(!Q.empty()){
        int u = Q.front(); Q.pop();
        if(a[u] == ss_st)
            ver.push_back(u);
        path.push_back(u);
        ss = ss + 1LL * a[u];
        for(int v : adj[u]) if(avail[v] && a[v] <= ss_st){
            avail[v] = false;
            Q.push(v);
        }
    }
    bool ok = false;
    for(int u : path)
    for(int v : adj[u]) if(a[v] <= ss && ans[v]){
        ok = true;
    }
    if(ok){
        for(int u : ver) ans[u] = true;
    }
    return;
}

void solve(){
    init();
    for(int u : list_[nn]){
        ans[u] = true;
    }
    for(int k = nn - 1; k >= 1; --k){
        memset(avail, true, sizeof(avail));
        for(int u : list_[k]) if(avail[u])
            bfs(u);
    }
    for(int i = 1; i <= n; ++i){
        if(ans[i])
            cout << 1;
        else
            cout << 0;
    }
    cout << "\n";
    return;
}

}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    // freopen("island.INP","r",stdin);
    // freopen("island.OUT","w",stdout);
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    for(int i = 1; i <= m; ++i){
        int x, y; cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    bool sub2 = true;
    for(int i = 1; i < n; ++i) if(a[i] < a[i + 1]){
        sub2 = false;
        break;
    }
    if(m != n - 1)
        sub2 = false;
    bool sub3 = true;
    if(adj[1].size() != 1 || adj[n].size() != 1)
        sub3 = false;
    for(int i = 2; i < n; ++i) if(adj[i].size() != 2)
        sub3 = false;

    if(n <= 2000 && m <= 2000){
        SUB1::solve();
    } else
    if(sub2){
        SUB2::solve();
    } else
    if(sub3){
        SUB3::solve();
    } else
        SUB4::solve();
    return 0;
}

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