oj.uz

Submission #637882

# Submission time Handle Problem Language Result Execution time Memory
637882 2022-09-03T13:45:16 Z DJeniUp Stranded Far From Home (BOI22_island) C++17
0 / 100
 487 ms 151632 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 139636 KB Output is correct
2 Correct 76 ms 139664 KB Output is correct
3 Correct 76 ms 139580 KB Output is correct
4 Incorrect 95 ms 139640 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 139584 KB Output is correct
2 Correct 78 ms 139644 KB Output is correct
3 Incorrect 365 ms 151632 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 139660 KB Output is correct
2 Incorrect 401 ms 151424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 139652 KB Output is correct
2 Incorrect 487 ms 151632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 139636 KB Output is correct
2 Correct 76 ms 139664 KB Output is correct
3 Correct 76 ms 139580 KB Output is correct
4 Incorrect 95 ms 139640 KB Output isn't correct
5 Halted 0 ms 0 KB -