Submission #993968

#	Time	Username	Problem	Language	Result	Execution time	Memory
993968		MarwenElarbi	Stranded Far From Home (BOI22_island)	C++17	10 / 100	222 ms	48124 KiB

island

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=2e5+5;
vector<int> adj[nax];
vector<int> newadj[nax];
int tab[nax];
int parent[nax];
long long sz[nax];
int ans[nax];
int find(int x){
    if(parent[x]==x) return x;
    return parent[x]=find(parent[x]);
}
bool sameset(int x,int y){
    return find(x)==find(y);
}
void joinset(int x,int y){
    x=find(x);
    y=find(y);
    parent[x]=y;
}
bool compare(int x,int y){
    if(tab[x]!=tab[y]) tab[x]>tab[y];
    else return x>y;
}
void precompute(int x,int p){
    sz[x]=tab[x];
    for(auto u:newadj[x]){
        if(u==p) continue;
        precompute(u,x);
        sz[x]+=sz[u];
    }
}
void dfs(int x,int p){
    for(auto u:newadj[x]){
        if(u==p) continue;
        if(sz[u]<tab[x]) continue;
        ans[u]=1;
        dfs(u,x);
    }
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<pair<int,int>> cur(n);
    for (int i = 0; i < n; ++i)
    {
        parent[i]=i;
        cin>>tab[i];
        cur[i]={tab[i],i};
    }
    for (int i = 0; i < m; ++i)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    sort(cur.begin(),cur.end());
    for (int i = 0; i < n; ++i)
    {
        sort(adj[i].begin(),adj[i].end(),compare);
    }
    for (int t = 1; t < n; ++t)
    {
        int i=cur[t].se;
        for(auto u:adj[i]){
            if(tab[u]<=tab[i]&&(!sameset(i,u))){
                joinset(i,u);
                newadj[i].pb(u);
                newadj[u].pb(i);
            }
        }
    }
    precompute(cur[n-1].se,-1);
    ans[cur[n-1].se]=true;
    dfs(cur[n-1].se,-1);
    for (int i = 0; i < n; ++i)
    {
        cout <<ans[i];
    }cout <<endl;
}

Compilation message (stderr)

island.cpp: In function 'bool compare(int, int)':
island.cpp:28:30: warning: statement has no effect [-Wunused-value]
   28 |     if(tab[x]!=tab[y]) tab[x]>tab[y];
      |                        ~~~~~~^~~~~~~
island.cpp:30:1: warning: control reaches end of non-void function [-Wreturn-type]
   30 | }
      | ^

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