oj.uz

Submission #1090410

# Submission time Handle Problem Language Result Execution time Memory
1090410 2024-09-18T10:46:50 Z jamkel Stranded Far From Home (BOI22_island) C++14
0 / 100
 104 ms 23968 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define st first
#define nd second
typedef long long ll;
ll f(vector<ll>&u,ll i)
{
    if(u[i]==i)
    {
        return i;
    }
    u[i]=f(u,u[i]);
    return u[i];
}
void f2(vector<ll>&u,vector<ll>&w,ll i)
{
    if(u[i]==i)
    {
        w[i]=2;
        return;
    }
    if(w[i]>0)
    {
        return;
    }
    f2(u,w,u[i]);
    w[i]=w[u[i]];
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);
    ll n,m;
    cin>>n>>m;
    vector<int>a(n);
    vector<pair<int,int>>c(n);
    vector<vector<ll>>b(n);
    for(int i=0;i<n;i++)
    {
        cin>>c[i].st;
        c[i].nd=i;
        a[i]=c[i].st;
    }
    sort(all(c));
    for(int i=0;i<m;i++)
    {
        ll x,y;
        cin>>x>>y;
        b[x-1].push_back(y-1);
        b[y-1].push_back(x-1);
    }
    vector<ll>u1(n);
    vector<ll>u2(n);
    vector<bool>wyn(n,false);
    for(int i=0;i<n;i++)
    {
        u1[i]=i;
        u2[i]=i;
    }
    for(int q=0;q<n;q++)
    {
        ll i=c[q].nd;
        ll wag=0;
        for(int j=0;j<b[i].size();j++)
        {
            if(a[b[i][j]]<a[i] or (a[b[i][j]]==a[i] && i>b[i][j]))
            {
                if(a[f(u1,b[i][j])]<a[i])
                {
                    wyn[f(u1,b[i][j])]=true;
                }
                wag+=a[u1[b[i][j]]];
                u2[u1[b[i][j]]]=i;
                u1[u1[b[i][j]]]=i;
                
            }
        }
        a[i]+=wag;
    }
    vector<ll>ww(n);
    for(int i=0;i<n;i++)
    {
        ww[i]=wyn[i];
    }
    for(int i=0;i<n;i++)
    {
        if(ww[i]==0)
        {
            f2(u2,ww,i);
        }
        cout<<ww[i]-1;
    }
    cout<<endl;
}

Compilation message

island.cpp: In function 'int main()':
island.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(int j=0;j<b[i].size();j++)
      |                     ~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 456 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 608 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 80 ms 23892 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 92 ms 22936 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 104 ms 23968 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 456 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 608 KB Output isn't correct
5 Halted 0 ms 0 KB -