oj.uz

Submission #714998

# Submission time Handle Problem Language Result Execution time Memory
714998 2023-03-25T17:15:42 Z aykhn Stranded Far From Home (BOI22_island) C++14
0 / 100
 465 ms 30024 KB 
#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]);
    }
}

int 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;

            if (get_sum(y) < arr[i].fi)
            {
                int z = get(y);
                for (int k = 0; k < d[z].size(); k++)
                {
                    ans[d[z][k]] = false;
                }
                d[z].clear();
            }

            unite(x, y);
        }
    }

    for (int i = 1; i <= n; i++) cout << ans[i];


}

Compilation message

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:114:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |                 for (int k = 0; k < d[z].size(); k++)
      |                                 ~~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Incorrect 10 ms 14548 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Incorrect 289 ms 29932 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Incorrect 360 ms 29468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Incorrect 465 ms 30024 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Incorrect 10 ms 14548 KB Output isn't correct
5 Halted 0 ms 0 KB -