제출 #757806

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
757806		thinkphp	Stranded Far From Home (BOI22_island)	C++17	100 / 100	465 ms	53456 KiB

island

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define OPT ios_base::sync_with_stdio(0); \
            cin.tie(0); \
            cout.tie(0)
 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define endl "\n"
#define all(v) v.begin(), v.end()
#define mpr make_pair
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define inf 0x3F3F3F3F
#define bpc __builtin_popcount
#define print(v) for(int i = 0; i < v.size(); i++) \
                    cout << v[i] << " "; \
                    cout<<endl;
 
ll n;
vector<ll> v(200001);
vector<ll> d[200001];
vector<ll> sum(200001);
vector<bool> ans(200001, true);
vector<ll> e(200001, -1);
vector<vector<ll>> adj(200001);
void init(int n)
{
    for (int i = 1; i <= n; i++)
    {
        d[i].pb(i);
        sum[i] = v[i];
    }
}
 
int get(int x)
{
    if (e[x] < 0) return x;
    return e[x] = get(e[x]);
}
 
int s(int x)
{
    return -e[get(x)];
}
 
void unite(int x, int y)
{
    x = get(x);
    y = get(y);
 
    if (x == y) return;
 
    if (e[x] > e[y]) swap(x, y);
 
    e[x] += e[y];
    e[y] = x;
 
    sum[x] += sum[y];
 
    for (int i = 0; i < d[y].size(); i++)
    {
        d[x].pb(d[y][i]);
    }
}
 
ll get_sum(int x)
{
    x = get(x);
    return sum[x];
}
 
int main()
{
    int m;
    cin >> n >> m;
    vector<pii> arr(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
        arr[i].fi = v[i];
        arr[i].se = i;
    }
 
    while (m--)
    {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
 
    sort(arr.begin() + 1, arr.end());
 
    init(n);
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < adj[arr[i].se].size(); j++)
        {
            int x = arr[i].se;
            int y = adj[x][j];
            if (arr[i].fi < v[y]) continue;
 
            int z = get(y);
 
            if (sum[z] < arr[i].fi)
            {
                for (int k = 0; k < d[z].size(); k++)
                {
                    ans[d[z][k]] = false;
                }
            }
 
            unite(x, y);
        }
    }
 
    for (int i = 1; i <= n; i++) cout << ans[i];
}

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

island.cpp: In function 'void unite(int, int)':
island.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < d[y].size(); i++)
      |                     ~~^~~~~~~~~~~~~
island.cpp: In function 'int main()':
island.cpp:105:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for (int j = 0; j < adj[arr[i].se].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~
island.cpp:115:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |                 for (int k = 0; k < d[z].size(); k++)
      |                                 ~~^~~~~~~~~~~~~

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