oj.uz

Submission #993968

# Submission time Handle Problem Language Result Execution time Memory
993968 2024-06-06T22:39:28 Z MarwenElarbi Stranded Far From Home (BOI22_island) C++17
10 / 100
 222 ms 48124 KB 
#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

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

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13404 KB Output is correct
2 Correct 2 ms 13488 KB Output is correct
3 Correct 193 ms 38736 KB Output is correct
4 Correct 152 ms 36432 KB Output is correct
5 Correct 202 ms 31928 KB Output is correct
6 Correct 193 ms 32336 KB Output is correct
7 Correct 191 ms 32576 KB Output is correct
8 Correct 204 ms 32596 KB Output is correct
9 Correct 173 ms 32340 KB Output is correct
10 Correct 163 ms 32964 KB Output is correct
11 Correct 179 ms 32896 KB Output is correct
12 Correct 174 ms 31100 KB Output is correct
13 Correct 163 ms 46408 KB Output is correct
14 Correct 157 ms 45036 KB Output is correct
15 Correct 184 ms 48124 KB Output is correct
16 Correct 149 ms 46932 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13404 KB Output is correct
2 Incorrect 218 ms 40828 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13404 KB Output is correct
2 Incorrect 222 ms 32392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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