제출 #1280146

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280146		Bui_Quoc_Cuong	Stranded Far From Home (BOI22_island)	C++20	100 / 100	196 ms	34428 KiB

island

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = a; i <= (int)b; i++)
#define FORD(i, a, b) for (int i = a; i >= (int)b; i--)
#define ll long long
const int maxn = 2e5 + 5;
int n, m;
vector <int> g[maxn];
int a[maxn];
namespace sub1
{

    void solve ()
    {
        FOR(i, 1, n)
        {
            ll cur = a[i];
            vector <int> vis (n + 2, 0);
            
            priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> pq;
            for (int &v : g[i]) pq.push(make_pair(a[v], v));

            vis[i] = 1;
            int cnt = 1;

            while (1)
            {
                bool ok = 0;
                while (!pq.empty() && pq.top().first <= cur)
                {
                    int u = pq.top().second;
                    pq.pop();
                    if (!vis[u])
                    {   
                        cur+= a[u];
                        vis[u] = 1;
                        cnt++;
                        ok = 1;
                        for (int &v : g[u]) if (!vis[v])
                        {
                            pq.push(make_pair(a[v], v));
                        }
                    } 
                }
                if (!ok)
                {
                    break;
                } else if (cnt == n)
                {
                    break;
                }
            }
            cout << (cnt == n);
        }
    }
}
namespace sub2
{
    int lab[maxn], vis[maxn];
    vector <int> can[maxn];
    ll sum[maxn];

    int find (int x) {return lab[x] < 0 ? x : lab[x] = find(lab[x]);}

    bool joint (int u, int v)
    {
        int x = find(u), y = find(v);
        if (x == y) return false;
        if (can[x].size() < can[y].size()) swap (x, y);
        lab[x]+= lab[y];
        lab[y] = x;
        sum[x]+= sum[y];    
        for (int &cc : can[y]) can[x].push_back(cc);
        can[y].clear();
        return true;
    }

    void solve ()
    {
        vector <pair <int, int>> sorted;
        FOR(i, 1, n)
        {
            lab[i] = - 1;
            can[i].push_back(i);
            sum[i] = a[i];
            sorted.push_back(make_pair(a[i], i));
        }       
        sort(sorted.begin(), sorted.end()); 
        int root = sorted.back().second;
        for (auto it : sorted)
        {
            int u = it.second;
            vector <pair <int, int>> cur_sorted;
            for (int &v : g[u]) if (vis[v])
            {
                if (sum[find(v)] < a[u])
                {
                    can[find(v)].clear();
                }
                cur_sorted.push_back(make_pair(sum[find(v)], find(v)));
            }
            sort(cur_sorted.begin(), cur_sorted.end());
            cur_sorted.resize(unique(cur_sorted.begin(), cur_sorted.end()) - cur_sorted.begin());   
            for (auto x : cur_sorted) joint (u, x.second);
            vis[u] = 1;
        }       
        vector <int> ans(n + 2, 0);
        for (auto it : can[find(root)]) ans[it] = 1;
        FOR(i, 1, n) cout << ans[i];
    }
}
signed main () 
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    #define kieuoanh "kieuoanh"
    if (fopen(kieuoanh".inp", "r")) 
    {
        freopen(kieuoanh".inp", "r", stdin); 
        freopen(kieuoanh".out", "w", stdout);
    }
    cin >> n >> m;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 1, m)
    {
        int u, v; cin >> u >> v;
        g[u].push_back(v); g[v].push_back(u);
    }
    // if (max(n, m) <= 2000) return sub1::solve(), 0;    
    return sub2::solve(), 0;
    return 0;   
}

컴파일 시 표준 에러 (stderr) 메시지

island.cpp: In function 'int main()':
island.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         freopen(kieuoanh".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
island.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen(kieuoanh".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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