Submission #637882

#	Time	Username	Problem	Language	Result	Execution time	Memory
637882		DJeniUp	Stranded Far From Home (BOI22_island)	C++17	0 / 100	487 ms	151632 KiB

island

#include "bits/stdc++.h"
#pragma GCC optimize("O3")

using namespace std;

typedef int ll;
typedef pair<ll,ll>pairll;
typedef long double ld;

#define fr first
#define sc second
#define pb push_back
#define INF 1000000000007
#define N 200007
#define endl '\n'
#define MOD 998244353

ll n,m,a[N],p[N],res[N],s[N],sz[N],h;

vector<ll>v[N];

queue<ll>q[N];

struct D{
    ll s,num;
}d[N];

bool mcp(D d1, D d2){
    return d1.s<d2.s;
}

ll A(ll x){
    if(a[x]!=x)a[x]=A(a[x]);
    return a[x];
}

void S(ll x,ll y,ll z){
    h--;
    //cout<<x<<" "<<y<<" "<<z<<endl;
    while(q[y].size()>0 && s[q[y].front()]<s[z]){
       // cout<<x<<" "<<y<<" "<<z<<" "<<q[y].front()<<" "<<endl;
        if(sz[A(q[y].front())]>=sz[x])p[q[y].front()]=z;
        q[y].pop();
    }
    if(rand()%2==0){
        swap(x,y);
    }
    if(q[x].size()<q[y].size())swap(q[x],q[y]);
    while(q[y].size()>0){
        q[x].push(q[y].front());
        q[y].pop();
    }
    sz[x]+=sz[y];
    a[A(y)]=A(x);
   // cout<<q[x].size()<<endl;
    return ;
}

ll R(ll x){
    if(x==0)return 0;
    if(res[x]!=-1)return res[x];
    res[x]=R(p[x]);
    return res[x];
}
 
int main()
{
    cin>>n>>m;
    h=n;
    for(int i=1;i<=n;i++){
        cin>>d[i].s;
        s[i]=d[i].s;
        sz[i]=s[i];
        d[i].num=i;
        a[i]=i;
        res[i]=-1;
        q[i].push(i);
    }
    for(int i=1;i<=m;i++){
        ll x,y;
        cin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    sort(d+1,d+1+n,mcp);
    for(int i=1;i<=n;i++){
        ll x=d[i].num;
        //cout<<"! "<<x<<endl;
        for(int j=0;j<v[x].size();j++){
            if(s[v[x][j]]<=d[i].s && A(x)!=A(v[x][j])){
                S(A(x),A(v[x][j]),x);
            }
        }
    }
    if(h!=1)exit(1);
    for(int i=1;i<=n;i++){
        //cout<<i<<" "<<p[i]<<endl;
        if(s[i]==d[n].s && h==1)res[i]=1;
    }
    for(int i=1;i<=n;i++){
        if(res[i]==-1)R(i);
    }
    for(int i=1;i<=n;i++){
        cout<<res[i];
    }
    cout<<endl;
    
    return 0;
}

Compilation message (stderr)

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

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