제출 #1351492

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1351492		Rares	Stranded Far From Home (BOI22_island)	C++20	0 / 100	1096 ms	20188 KiB

island

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN=2e5+10;

int n,m,a[MAXN],rez[MAXN];
vector <int> g[MAXN],gd[MAXN];
bool cmp (int x, int y){
    return a[x]<a[y];
}

int vi[MAXN];
struct DSU{
    int tata[MAXN],s[MAXN],st[MAXN];
    void init (){
        for (int i=1;i<=n;++i){
            tata[i]=i;
            s[i]=1;
            st[i]=a[i];
        }
    }
    int radacina (int node){
        if (tata[node]==node) return node;
        return tata[node]=radacina (tata[node]);
    }

    bool unire (int x, int y){
        x=radacina (x);
        y=radacina (y);
        if (x==y) return false;
        gd[x].push_back (y);
        gd[y].push_back (x);
        if (s[x]<s[y]) swap (x,y);

        tata[y]=x;
        s[x]+=s[y];
        st[x]+=st[y];
    }

    void dfs (int node, int prevn){
        rez[node]=1;
        for (auto x:gd[node]){
            if (x==prevn or rez[x]) continue;
            dfs (x,node);
        }
    }
}dsu;


signed main()
{
    ios_base::sync_with_stdio (false);
    cin.tie (nullptr);

    cin >>n>>m;
    for (int i=1;i<=n;++i){
        cin >>a[i];
    }
    for (int i=1;i<=m;++i){
        int x,y;
        cin >>x>>y;
        g[x].push_back (y);
        g[y].push_back (x);
    }

    for (int i=1;i<=n;++i){
        sort (g[i].begin (),g[i].end (),cmp);
    }

    vector <int> v(n);
    for (int i=1;i<=n;++i) v[i-1]=i;
    sort (v.begin (),v.end (),cmp);
    dsu.init ();


    for (auto node:v){
        int crt=dsu.radacina (node);
        int val=dsu.st[crt];

        for (auto x:g[node]){

            ///intr-un nod neprocesat inca
            if (a[x]>val){

                if (rez[crt]==0) dsu.dfs (crt,crt);
            }
            else{
                dsu.unire (crt,x);
                crt=dsu.radacina (node);
                val=dsu.st[crt];
            }
        }
    }

    for (int i=1;i<=n;++i){
        cout <<1-rez[i];
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

island.cpp: In member function 'bool DSU::unire(long long int, long long int)':
island.cpp:38:14: warning: control reaches end of non-void function [-Wreturn-type]
   38 |         st[x]+=st[y];
      |         ~~~~~^~~~~~~

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