oj.uz

Submission #580171

# Submission time Handle Problem Language Result Execution time Memory
580171 2022-06-20T16:40:35 Z wdjpng Stranded Far From Home (BOI22_island) C++17
0 / 100
 1000 ms 44924 KB 
#include <bits/stdc++.h>

#define int long long
#define double long double
#define rep(i,n) for(int i =0; i<n; i++)
#define all(a) a.begin(),a.end()

using namespace std;

int n,m;
vector<int>s;
vector<vector<int>>E;
vector<int>chef(2e5+1);

struct uni
{
    int sum=0;
    set<int>bord;
};

vector<uni>unis(2e5+1);

int find(int a)
{
    if(a==chef[a]) return a;
    return chef[a]=find(chef[a]);
}

void unite(int a, int b) {
    a=find(a);
    b=find(b);
    if(unis[b].bord.size()>unis[a].bord.size()) swap(a,b);
    for(int i : unis[b].bord) if(!unis[a].bord.count(i)) {unis[a].sum+=s[i]; unis[a].bord.insert(i);}
}

bool sorti(int a, int b)
{
    return s[a]<s[b];
}
signed main()
{
    cin>>n>>m;
    if(n==1) {cout<<"1\n"; exit(0);}
    s.resize(n);
    rep(i,n) cin>>s[i];

    E.resize(n);
    rep(i,m)
    {
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }

    rep(i,n)
    {
        chef[i]=i;
        unis[i].bord.insert(i);
        unis[i].sum=s[i];
    }

    vector<int>ord(n);
    rep(i,n) ord[i]=i;

    int totsum=0;
    rep(i,n) totsum+=s[i];

    sort(all(ord), sorti);
    vector<bool>sol(n,false);
    for(int v : ord)
    {
        set<int>nodes;
        int sum = 0;
        sum+=s[v];

        nodes.insert(v);

        bool ischange=true, halt=false;
        while (ischange&&!halt)
        {
            ischange=false;
            for(int i : nodes)
            {
                for(int w : E[i])
                {
                    if(s[w]<=sum&&(nodes.count(w)==0))
                    {
                        nodes.insert(w);
                        sum+=s[w];
                        ischange=true;
                        halt|=sum==totsum||sol[w];
                    }
                    if(halt) break;
                }
                if(halt) break;
            }
        }
        sol[v]=halt;
    }

    rep(i,n) cout<<(sol[i]?'1':'0');
    cout<<'\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 8 ms 12756 KB Output is correct
3 Correct 7 ms 12756 KB Output is correct
4 Correct 14 ms 13028 KB Output is correct
5 Correct 26 ms 13140 KB Output is correct
6 Correct 11 ms 13012 KB Output is correct
7 Correct 12 ms 13216 KB Output is correct
8 Correct 12 ms 13044 KB Output is correct
9 Execution timed out 1093 ms 13124 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 7 ms 12756 KB Output is correct
3 Execution timed out 1095 ms 37680 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Execution timed out 1093 ms 44924 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Execution timed out 1097 ms 44724 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 8 ms 12756 KB Output is correct
3 Correct 7 ms 12756 KB Output is correct
4 Correct 14 ms 13028 KB Output is correct
5 Correct 26 ms 13140 KB Output is correct
6 Correct 11 ms 13012 KB Output is correct
7 Correct 12 ms 13216 KB Output is correct
8 Correct 12 ms 13044 KB Output is correct
9 Execution timed out 1093 ms 13124 KB Time limit exceeded
10 Halted 0 ms 0 KB -