제출 #1267186

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1267186		DangKhoizzzz	Stranded Far From Home (BOI22_island)	C++20	10 / 100	133 ms	27356 KiB

island

#include <algorithm>
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;

const int INF = 1e18;
const int maxn = 2e5 + 7;
const int mod = 1e9;

int n, m, a[maxn];
vector <int> g[maxn];
bool vis[maxn];


namespace sub1
{
bool check()
{
    if(n <= 2000 && m <= 2000) return 1;
    return 0;
}
void solve()
{
    priority_queue <pii> Q;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++) vis[j] = 0;
        vis[i] = 1;
        int cur = a[i];
        for(int v: g[i]) Q.push((pii)
        {
            -a[v], v
            });

        while(!Q.empty())
        {
            auto tmp = Q.top();
            Q.pop();
            int u = tmp.se;
            if(vis[u]) continue;
            if(a[u] > cur) break; // skip instead of break!
            vis[u] = 1;
            cur += a[u];
            for(int v: g[u])
                if(!vis[v]) Q.push({-a[v], v});
        }
        cout << (all_of(vis+1, vis+n+1, [](bool x)
        {
            return x;
        }) ? 1 : 0);

    }
}
};

namespace sub2
{
bool check()
{
    for(int i = 2; i <= n; i++)
    {
        if(a[i] > a[i-1]) return 0;
    }
    return 1;
}
int sum[maxn];
bool mark[maxn];
void dfs(int u, int p)
{
    sum[u] = a[u];
    for(int v: g[u])
    {
        if(v == p) continue;
        dfs(v, u);
        sum[u] += sum[v];
    }
}
void go(int u, int p)
{
    if(sum[u] >= a[p]) mark[u] = 1;
    else return;
    for(int v: g[u])
    {
        if(v == p) continue;
        go(v, u);
    }
}
void solve()
{
    dfs(1, 0);
    go(1, 0);
    for(int i = 1; i <= n; i++) cout << mark[i];
}
}

namespace sub4
{
void solve()
{

}
}


void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    if(sub1::check()) sub1::solve();
    else if(sub2::check()) sub2::solve();
    else sub4::solve();
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

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