oj.uz

답안 #993967

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
993967 2024-06-06T22:39:06 Z MarwenElarbi Stranded Far From Home (BOI22_island) C++17
0 / 100
 2 ms 13656 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(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    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 | }
      | ^
island.cpp: In function 'int main()':
island.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
island.cpp:50:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 13656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 13404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 13404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 13404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 13656 KB Output isn't correct
2 Halted 0 ms 0 KB -